Recursions and Lists and Slices
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'
andword[1:]
is'bcdefghij'
. -
Second time around -
word
is the previousword[1:]
. Soword[0]
is'b'
andword[1:]
is now'cdefghij'
. -
Keep looping until there there are no letters left in
word
and thenword[]==""
.
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
- theword[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.