Session 9: Recursion - Modulue A: Recursion

1. Overview

What is recursion?
What is a base conditional?

2. What is Recursion?

Recursion is the process of having a function call itself to perform a loop. There are two conditionals that make up a recursive function: the base conditional and the recursive conditional. For this example we will create a recursive method to print stars. The function declaration is:

def stars(x):

The base conditional determines when a function should stop looping. When your function enters the base conditional it should return a value. The base conditional for the stars function is:

    if x == 1:
        return "*"

The recursive conditional is in charge of maintaining all looping of the function. When creating the recursive conditional your goal is to end up in the base conditional. The recursive conditional for the stars function is:

    else:
        return "*"+stars(x-1)

When we put all these pieces of code together it looks like this:

def stars(x):
    if x == 1:
        return "*"
    else:
        return "*"+stars(x-1)

Here is a diagram showing what happens when you call stars(3):

Lets go over these questions using the diagram of stars(3):

• What is returned?
• How many times is stars called?
• How many times is the base conditional entered?
• How many times is the recursive conditional entered?

3. Recursion and Fibonacci

Now that we have discussed what recursion is and how to use it, let's practice creating some recursive functions. On Tuesday we programmed the Fibonacci sequence using for loops. Now we are going to create a function that calculates the Fibonacci sequence recursively.

1. Download the program fibRecurse.py into your programs directory. Remember to add the .py to the end of the program so you can open it in IPython once you're done.
2. Open the terminal window.
3. Change the directory to your programs directory with the cd command.
4. Open fibRecurse.py in gedit using: gedit fibRecurse.py &
5. Read the instructions and write the code after the "Code goes here: " comment!

Start by doing the first exercise.

There are examples on this page that you can experiment with! Don't be afraid to copy the code into your program and play around with it. In the second exercise we will try to code the Fibonacci sequence. It might be a good idea to get out a scratch piece of paper and add up the first four or five numbers.

Don't be afraid to ask questions! We are always here to help.

1. Start IPython with the ipython command.
2. Test out each section of code in your terminal before moving on.
3. You can run your program by typing run fibRecurse.py.

Make sure that you try running the program after each excercise that you create! That way, if it doesn't work, it's a lot easier to figure out what's going on!

Take a screenshot of your output and please answer these questions on your webpage.