# Recursions and Lists and Slices

Thu 18 December 2014

Filed under Python

## Recursions on lists .. with slices

Following up on my post about recursions. This time about recursive functions using a list.

So here's where slices gets really useful.

As a quick reminder about slices: Slices allow you to get a substring from a string or part of a list. The syntax is string_or_list(start, end, step) More about slices

Some examples

word = 'abcdefghij'

a b c d e f g h i j
0 1 2 3 4 5 6 7 8 9

*Notice that there are 10 positions here. Starting with 0. ('a' is in the 1st position. 'j' is in the 10th position.)

syntax result explanation
word[0] a # index 1st position
word[-2] i # index 2nd to last position
word[7] h # index 8th position
word[7:9] hi # slice FROM 8th position UNTIL 10th position (not inclusive) 8th & 9th (indexes 7,8)
word[:6] abcdef # slice FROM BEGINNING until 7th position (indexes 0-6)
word[5:] fghij # slice FROM 6th position until END (indexes 5-->)
word[::3] adgj # slice FROM BEGINNING until END, STEP 3 (indexes 0,3,6,9)
word[3::2] dfhj # slice from 4th position until end, STEP 2 (3,5,7,9)

One way to remember how slices work is to think of the indices as pointing between characters, with the left edge of the first character numbered 0. Then the right edge of the last character of a string of n characters has index n.

Ok, so that's about slices. Here's why slices work so well with recursive.

Let's work with `word = 'abcdefghij'`.

• First time around `word[0]` is`'a'` and `word[1:]` is `'bcdefghij'`.

• Second time around - `word` is the previous `word[1:]`. So `word[0]` is `'b'` and `word[1:]` is now `'cdefghij'`.

• Keep looping until there there are no letters left in `word` and then `word[]==""`.

Let's see that in action. Here's the code:

```word = 'abcdefghij'

def print_letters(word):
print 'word: "{}"'.format(word)
if word == "":
print 'hit the base case. the end'
return word
else:
print "in the 'else statement'"
print word[0]
return print_letters(word[1:])

print_letters(word)
```

So what happened here?

• Each recursion starts off by printing what `word` looks like now.

• Then it checks for the 'base case', the exit of the loop. Here it is `if word == "":`

• If not the 'base case', then the recursion happens. Here, it is the same function with a new `word` - the `word[1:]` in the return.

• And it loops and loops until it hits the 'base case' and exits.

That was a simple examples using slices and strings. Here's another with lists.

```numbers = [10, 4, 19, 7, 8]

def max(numbers, largest_so_far=0):
print numbers
print largest_so_far

next_num = numbers[0]

if numbers == []:
return largest_so_far

if next_num > largest_so_far:
return max(numbers[1:], largest_so_far=next_num)
else:
return max(numbers[1:], largest_so_far=largest_so_far)
```

So what's happening here.

This function seeks to find the largest number in the list.

`def max(numbers, largest_so_far=0):` : We define the function called `max` with 2 arguments: `numbers`, which is the list of numbers from which to find the largest number. And `largest_so_far` in which we will hold onto the 'largest number found up to that point' and we start it with a default of `0`.

`ext_num = numbers[0]` : Which number in the list are we comparing? It is always the first number of the new list. See the 'else statement' where we make the make the new argument for the recursive function `numbers[1:]`. It is the previous list - but from the second position.

`if numbers == []:` : This is the base case, the exit of the loop. If there are no more numbers, then the `largest_so_far` is the largest number. The end!

`if next_num > largest_so_far:` : if `next_num` is larger than `largest_so_far`, then ...

`return max(numbers[1:], largest_so_far=next_num)` : do this function again - with the arguments: `numbers[1:]` and `largest_so_far=next_num`.

`else:` : if `next_num` is not larger (is equal to or less than), then ...

`return max(numbers[1:], largest_so_far=largest_so_far)` : call the recrusive function again - like above, but leave the `largest_so_far` as is.

And the loop continues until hits base case.