Udacity CS 101: Recursive

UPDATE: I wrote this post before heading to Chapter 12 of Unit 6, and I just realized that this post contains the answer to the question! So stop readying if you have not attempted!

You might remember seeing this term somewhere in my blog before, and today we are going to visit recursive functions again, under the guidance of Professor Evans. Recall the Fibonacci sequence

1, 1, 2, 3, 5, 8, 13, 21 ...

1, 1, 2, 3, 5, 8, 13, 21 …
Image courtesy of Wolfram MathWorld

1, 1, 2, 3, 5, 8, 13, 21 …

Each number is the sum of its two preceding numbers ( 2 = 1 + 1, 21 = 8 + 13).

In every recursive definition, there are two cases, the base case, and the recursive case. The base case is a starting point, which is not defined in itself. This means that it has a value which we already know before any evaluation is done. In the case of the Fibonacci sequence, there are two base cases: the first two 1s. The recursive case is defined in terms of smaller versions of itself, which will repeatedly define in a smaller scope such that it reaches the base case. It will probably be clearly in the code below:

def fib(n): # n is the position of the number in the sequence

if n == 1:

return 1

if n == 2:

return 1

return fib(n-1) + fib(n-2)

i = 1
while i < 11:

print fib(i)
i += 1

The procedure fib() takes in a single parameter n, which is the position of the number in the sequence which you wish to find the value of. If n is 10, it means that you want to find the value of the tenth number in the sequence. Here you can see our base cases very clearly: when the value n is 1 and 2, the value returned is both 1. This means that the first and second number in the sequence is both 1.

If we want to find the third number in the sequence, we pass in n = 3: here is where the magic happens:

  1. fib(3) is evaluated, and since 3 is neither 1 nor 2, the procedure returns fib(n-1) + fib(n-2), which is fib(2) + fib(1)
  2. Doesn’t this look familiar, fib(2) is the second number in the sequence, which is 1, and fib(1) is the first number, which is also 1. Hence fib(3) = 1 + 1 = 2! Nice!

So what if we try something like fib(999)? Okay prepare yourself:

  1. (no just kidding we’ll do fib(5)) fib(5) will return fib(4) + fib(3)
  2. fib(5) = fib(4) + fib(3)
  3. fib(4) will return fib(3) + fib(2), fib(3) will return fib(2) + fib(1)
  4. fib(5) = fib(3) + fib(2) + fib(2) + fib(1)
  5. fib(3) will return fib(2) + fib(1), and all fib(2) and fib(1) will return 1
  6. fib(5) = fib(2) + fib(1) + 1 + 1 + 1
  7. fib(5) = 1 + 1 + 3
  8. fib(5) = 5!

You can definitely copy the code into python and try a fib(99999), but I think it’ll take a while to complete.

This Udacity post references Udacity CS 101 Unit 6 Chapters 6, 7, 8, 9 and 12.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s