CS 241 - Data Structures

07 Prove : Homework - Data Structures

Recursion

Outcomes

At the end of this study, successful students will be able to:

Articulate the strengths and weaknesses of recursion.
Use recursion in Python to solve problems.

Overview

To prepare us for a few of the upcoming data structures and algorithms we will study, we need an additional tool in our tool belt: Recursion.

At this point, we are comfortable having functions call other functions. And even having function A call B, then B call C, and even C call D doesn't really scare us very much. The computer doesn't somehow lose track of where it is or the value of variables in function A just because other functions are being called.

But what if function A called itself? Is that even legal? Does it just cause an error? This is called recursion.

Preparation Material

Please read the following:

TopCoder: An Introduction to Recursion

Using Recursion in Python

When it comes to using recursion in Python, there is no difference between a function calling itself, and a function that calls a different one. The only trick is to make sure there is a way to stop the recursion (i.e., a base case).

Consider the task of a countdown function that counts from a given number down to 1. While this problem could certainly be solved with a loop (and in this case that is an easier/better solution), it can be solved via recursion and can illustrate the necessary components. For example, if you consider the case of starting with 5. You could view the problem as displaying 5, followed by a countdown beginning with 4.

The following code shows how to define this function in terms of a call to the next number, which is 1 smaller.


def countdown(num):
    print(num)

    next_num = num - 1
    countdown(next_num)

    # Note, we still need a base case...

The next task is to find a base case. This is the time when the function should stop calling itself and return. We want this case to be as simple as possible. For this problem, we could choose 1, where the logic would require displaying 1, and then returning. We could also choose 0, which is an even easier case: we don't display anything just return.

The following code is updated to include a base case. We often include these at the top of the function.


def countdown(num):
    if num == 0:
        return

    # We could use an "else" here, but we really don't have to because
    # the return statement from the line above will end the function
    # right there for the base case. Then, anything that follows is the
    # recursive case

    print(num)

    next_num = num - 1
    countdown(next_num)

Finally, two other things to simplify the function. First, we don't need to create a separate variable for next_num, but can just subtract 1 from our variable right in the function call. Second, while the base case works by checking for 0, if by some accident we skipped over 0 and got to -1, this could would not stop (until an error occurs). To safeguard against this, we can change our check to be "<= 0" to ensure that it stops in this case as well.

The following code shows an updated, simplified recursive solution to the countdown problem:


def countdown(num):
    # Check for the base case
    if num <= 0:
        return

    # do the work of the function
    print(num)

    # make the recursive call
    countdown(num - 1)

Homework Assignment

Write a program that uses recursion to compute the n-th item in the Fibonacci sequence. Refer to the wikipedia article: Fibonacci Number for more information about this sequence.

Instructions

Follow these steps to guide you through the process:

Identify how the n-th item can be expressed in terms of other Fibonacci numbers.
Identify the base case(s) to stop the recursion. (There may be more than one. This takes a little bit of thinking.)
Write a function, def fib(n), that computes the Fibonacci number at index n.
Do not pass any other variables to this function, it should be able to compute this using only the index.
Write a main function that asks the user for the index of the Fibonacci number they want to compute. It should then pass this to your fib function, and display the result.
Test your program with several different values of n.

As far as the first number in the sequence, you can assume that fib(0) is 0, fib(1) is 1, and fib(2) is 1.

Sample Output


Enter a Fibonacci index: 7
The Fibonacci number is: 13

Testing your program

An automated testBed script is not available for your program. Instead please manually test your program with the following values (and verify that you receive the expected result):

fib(0) -> 0
fib(1) -> 1
fib(7) -> 13
fib(14) -> 377
fib(20) -> 6765

Submission

You are encouraged to work with others on the programming and the quiz.

When you have a good understanding of this data structure and have completed the programming project, take the accompanying I-Learn quiz. It has questions about how the data structure works and also has places for you to report on the parts of the programming assignment that you completed.

OO Programming and Data Structures | CS 241