Question

In lecture 4, the Fibonacci function, can someone walk me step by step through what the function is actually doing? Thanks!

Answer 1

Which one, the recursive or the iterative one?
I will assume that it is the recursive one (because it causes more confusion), you have to think this way: first, you find a solution to a smaller problem (as simple as possible, in this case, the base case of n == 1 or n == 0 -> return 1 or 0 (because fib(0) == 0, fib(1) == 1)), then you actually want to "unwrap" the problem until it reaches the base case. Think about it this way: it's a stack, that you only have one way out: to return 1 whenever n == 1 or 0 if n==0; until it gets there, you want to "remove" from the stack bigger instances of the problem. You aren't really calculating fib(5), you are actually calculating all the way until it reaches the base case, like fib(4) + fib(3), but fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), etc..., that returns the same result, but has a subtle difference: the program only "knows" how to handle fib(1) or fib(0), it will return a solution if and only if it reaches the base case.
During the computation, it doesn't know how much fib(3) is worth, only that it should call fib(2) and fib(1). It's a sufficient case for this algorithm, because we are sure that the problem is getting nearer the base case in each recursive call, but this might be untrue for other cases. If you want to go more in depth about these ideas, look for optimal substructures and recurrence relations. If I rambled too much and made myself unclear, go ahead and ask again. I might be able to be clearer, or someone may explain more concisely and clearer than I would ever be able to.

Answer 2

http://codepad.org/XqjMKPps

Answer 3

Thanks for the replies bwCA and bmp!

I should warn that this is really my first ever experience with programming. Conceptually, I get the idea behind recursion (correct assumption, bmp), but I suppose what I don't get is in this case, what would prompt a final output of anything but 1?

In lecture, the output returned is: fib(12) = 233; fib(24) = 75025, etc. When I put the code from lecture (and the handout) into codepad, there is no output. http://codepad.org/eM8DHZYu

For that matter, the same holds true for the isPalindrome function: http://codepad.org/H0CdI8EB Perhaps I'm missing something in codepad?

Logically, it makes more sense to me that there would be no output, because the only actual value I see that fib(x) could ever return is 1. And, if I understand correctly, when that occurs, the program would stop calling fib, and move on, right?

So, I'm just not seeing what causes an output of 233, for example.

Thanks for your patience with a newbie, and thanks for your help!

Answer 4

What is actually happening is that, whenever it reaches the base case (fib of 1 and fib of 0), it returns an actual value: 1. But, then, it moves up in the "stack", It now knows how to solve fib(2). Solving fib(2), it knows what value to put for the fib(3) call. Truth be told, you aren't really calculating fib(4) and fib(3) when you call fib(5). It really is something like that:\[Fib(5) = Fib(4) + Fib(3) \rightarrow Fib(5) = Fib(3) + Fib(2) + Fib(2) + Fib(1)\]
and then: \[Fib(5) = Fib(2) + Fib(1) + Fib(1) + Fib(0) + Fib(1) + Fib(0) + Fib(1)\] Finally: \[Fib(5) = Fib(1) + Fib(0) + Fib(1) + Fib(1) + Fib(0) + Fib(1) + Fib(0) + Fib(1)\]
Now, what is actually happening is a kind of summation of the base cases, up to the actual value of Fib(5) (8), and that is why there is actually an output. Hopefully, that made sense.
And your code pasted at codepad works fine for me, maybe codepad is bugged now, don't know.

Answer 5

Damn, I lost my entire answer, T_T. Anyway, what I wrote there is that, you have to think this way: when the program first reaches the else block, it puts the program on a halt, waiting for fib(n-1) + fib(n-2) to be processed and to return an actual value. This also happens to the calls for fib(n-1) and fib(n-2), etc. Most importantly, the outermost program is still running, waiting for fib(n-1) and fib(n-2) to return some value, so it can evaluate fib(n-1) + fib(n-2) and return the result. It's like several instances of the same program are running at the same time with different values for n, until it reaches a base case, where there is an actual value (1), and it, then, can solve for the running instances of the program. Visually: