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.

Recursions and Lists and Slices

Recursions on lists .. with slices

Comments