Unit 3 - Recursion

Table of Contents

1. Overview
2. Recursion
3. Visual Recursion
4. More difficult recursion

3.1. Overview

Visual recursion on a box of hot chocolate mix

Recursion is an important topic in computer science, probably the most important topic that doesn't get covered well in most introductory computer science courses. That's partly because it can be a little confusing at first, and maybe because the concept of recursion—drilling down deeper and deeper into the memory of the computer, with the possibility of never getting out alive—is a little scary, at least existentially.

Using recursion and "thinking recursively" is an important skill in computer science, and we're going to spend a good part of our time in this course doing just that: using recursion and thinking recursively.

Let's get started!

3.2. Recursion

Let's take a look at a specific example.

3.2.1. Simple looping with recursion

Here's a simple loop that we can write recursively. Given a counting variable i that starts at an initial value, and an end value n, this recursive loop counts from 1 to n (exclusive):

def loop(i, n):
    """recursively counts from i to n - 1"""
    if i >= n:
        return
    else:
        print(i)
        loop(i + 1, n)

# demonstrate the loop function
loop(1, 4)

To fully understand what's happening when this code executes, it may be helpful to look at the output from an interface like that available at pythontutor.com:

3.2.2. Summing values in a loop, versus recursively

If we want to write a function to add the values from 1 through n using a loop, it's not too difficult:

def loop_sum(n):
    sum = 0
    for i in range(1, n + 1):
        sum += i
    return sum

This code runs just fine.

We can also write a recursive version of this function, a version in which the function calls itself. One of the keys to doing this is think about what's happening when we add those numbers. If I want to add the numbers from 1 to 10, I can think about that sum as being 10 + the sum of all the lower numbers 1 through 9.

I might write it like this: The sum of numbers 1-10 = 10 + the sum of numbers 1-9.

What is the sum of the numbers 1-9, though? Isn't that just 9 + the sum of numbers 1-8?

Likewise, The sum of numbers 1-8 = 8 + the sum of numbers 1-7. There's a pattern emerging here.

Take a look at this function:

def sum(n):
    return n + sum(n - 1)

That's single line of code in this function returns a value that includes n + the sum of the numbers lower than n. When the sum() function calls itself, that's the recursive part of this function.

It's a clever way of looping that is actually much simpler and cleaner than the loop_sum written above. It might even be easier to conceptualize, at least if you're comfortable with the concept of recursion.

I ran into a problem when I actually tried to run this code, however:

print sum(10)
File "", line 2, in sum
File "", line 2, in sum
.
.
.
File "", line 2, in sum
RecursionError: maximum recursion depth exceeded

The reason this function ran into trouble is that it never identified a way for it to stop calling itself. At some point, we need the function to be able to tell itself that it shouldn't call itself anymore.

How do I know when I'm done adding the numbers from n on down? Once n gets down to the value 1, I shouldn't call the function recursively again. I just want to send back the value of 1.

def sum(n):
    if n == 1:
        return 1
    else:
        return n + sum(n - 1)

This program works correctly.

Make sure you understand exactly what's happening here.

1. We define a function which, as part of its description, calls itself in a slightly modified form.
2. We call the function ( def sum(10) for example) with a specific value, which will be identified as n during the that call.
3. When the function calls itself again with the value n - 1, all of the values for that first function call are kept in memory, and the new function call creates a new "state" in memory with the new values (n - 1 for n, etc.).
4. This process continues, which each new function call generating a new instance of itself in memory until the limiting condition is met.
5. The return instruction exits from the current state, and the program returns to processing the previous state of the function.
6. This process of calling functions and returning from their states continues until the very first function call returns a value. At that point the recursive process has completed.

3.2.3. Factorial recursion

Summing the values from 1 to n is a nice simple introduction to recursion. Now try this.

def fact(n):
    if n == 1:
        return 1
    else:
        return n * fact(n - 1)

3.2.4. Accidental recursion

Based on what you know about recursion to this point, take a look at the problem below.

def play_game():
    # code to play game of blackjack
    # more code
    continue = input(“Play again (y/n)? ")
    if continue == "y":
        play_game()

def play_game():
    print("Let's play the game!")
    play_game()

play_game() # call the function the first time

3.2.5. Fibonacci recursion

You almost certainly know the Fibonacci sequence, which begins with the values 0 and 1. Each successive value in the series is based on the sum of the previous two values.

The Fibonacci is an appealing and intuitive function, and its perfectly suited for solving recursively.

Try out the problem recursive_fibonacci.

3.3. Visual Recursion

There are obvious "visual recursions" like the hot chocolate can above, or a series of nested Russian dolls, with each doll of size n containing a smaller doll of size n - 1, down to some final size.

It's fun to draw graphical recursions using computer graphics as well. You'll want to use either Python's native turtle module or the Processing app from processing.org.

The ultimate visual recursion

Show/hide recursion

 

3.3.1. turtle graphics

The turtle module was built into Python from the beginning, and is a nod to Seymour Papert, an educational theorist at MIT who felt that computers, when used by students at an early age, would revolutionize the way people learn and think. (His efforts in this area are document in the book Mindstorms. If you're interested in reading it, let me know and I'll give you a copy.)

The general idea behind turtle graphics is that you can consider a turtle in the middle of the computer screen, facing to the right, with a pen attached to its tail, and the tail currently "down" so that the pen will draw a line across the screen when the turtle moves.

You can give the turtle a series of commands, telling it to put the tail "up" or "down", telling it to go forward or back a certain distance, telling it how many degrees to rotate in place, telling it to move to a given location on the screen.

Try out turtle_basics to get a feel for how turtle graphics commands work.

3.3.2. The Processing application

The Processing application you can download at at processing.org. See an introduction to using Processing in a Python environment here. For most of the activities below it'll be a bit easier to use the turtle module, but it you're going to be trying out the Mandlebrot plot, you should definitely check out Processing.

3.3.3. Projects

Once you've got your graphics all set up , pick two or three of the following options and give them a try!

• turtle_recursion
• recursive_tree

3.4. More Difficult Recursion

We'll have the chance to explore some more complex recursion a little later on in this course. For now, let's take a look at two standard applications of recursion: solving the "Towers of Hanoi" puzzle and navigating a maze.

3.4.1. The Towers of Hanoi

The Towers of Hanoi is a classic problem which we'll demonstrate in class.

This problem lends itself quite nicely to a recursive solution: each move, you're moving a disk from a source tower to another tower.

Consider what happens if we have Tower A with two disks on it and we're trying to get them all over to Tower C. The general strategy: move all the top disks to B, then move A to C, then move all the disks from B to C.

We'd use the exact same strategy with three disks...

But how do we code that?

3.4.1.1. Towers of Hanoi solution (given via instructions)

towers-v1-simple-student.py

3.4.1.2. Towers of Hanoi solution (demonstrated with lists)

towers-v2-list_version.py

3.4.1.3. Towers of Hanoi (visualized)

It's easy to gloss over the process of recursion when you're looking at simple examples, but a fundamental understanding of what's going on is important.

To make sure you have a solid understanding of what's happening through this process...

# Program to demonstrate Recursive Towers of Hanoi

def display():
    print("----------")
    print("A",A)
    print("B",B)
    print("C",C)
    
def move(height,source, inter, dest):
    if height == 1:
        dest.append(source.pop())   # Move a lone disk from a tower
    else:
        move(height - 1,source, dest, inter)
        dest.append(source.pop())   # Move a single disk from a tower
        move(height - 1,inter, source, dest)

def main():      
    global A, B, C  # makes these available to display function
    A= [3, 2, 1]
    B = []
    C = []
    display()       # display start of problem
    move(3, A,B,C)  # solve problem recursively
    display()       # display state at end of problem


main()