I do not understand (C++)

[sincka]

I've been trying to fully understand this code for two days:


1: // Listing 5.10 - demonstrates recursion
2: // Fibonacci find.
3: // Finds the nth Fibonacci number
4: // Uses this algorithm: Fib(n) = fib(n-1) + fib(n-2)
5: // Stop conditions: n = 2 || n = 1
6:
7: #include <iostream.h>
8:
9: int fib(int n);
10:
11: int main()
12: {
13:
14: int n, answer;
15: cout << "Enter number to find: ";
16: cin >> n;
17:
18: cout << "\n\n";
19:
20: answer = fib(n);
21:
22: cout << answer << " is the " << n << "th Fibonacci number\n";
23: return 0;
24: }
25:
26: int fib (int n)
27: {
28: cout << "Processing fib(" << n << ")... ";
29:
30: if (n < 3 )
31: {
32: cout << "Return 1!\n";
33: return (1);
34: }
35: else
36: {
37: cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n";
38: return( fib(n-2) + fib(n-1));
39: }
40: }


It is an example from a book. I've been reading over and over the example and the example explanation and I just do not understand how the program (recursion) works.

If anyone would bother to explain this code it would be very much appreciated.

Well I'm gonna go back to studying the code :confused:

Thanx guys... later.

[sincka]

Oh and I forgot... the program has bugs. If you figure out what they are kewl. But all I want is to know how the program (recursion) actually operates.

[Marcel2008]

Hello,

The fib function calls itself again, when the fibnumber < 3. This is called recursion, a function / method that calls itself.

Instead of using a loop, you could use a recursive function.

The listing does contain a bug, i'll give you a hint. Look how the fibionacci numbers work, is recursion a good way to calculate this?

Good luck!

[sincka]

Thank you for the reply marcel :)

I would ask someone to give me an easier example of recursion (with comments if possible). I am really confused about the line 38 in the program above.

I would think that the maximum return value of that line is 2 since each time that n < 3 it returns a value of 1. The line loops untill it gets what it wants (n < 3) which returns 1 to line 38. Therefore 1+1 is two... we learn that in grade 1 :p

Anyway... I am really confused about this (I don't even know if any of my confusions above make sense but hey) and help would be VERY appreciated.

[Marcel2008]

That's the bug in the listing.
Recursion isn't the best method for calculation fibionacci numbers.

I know this is confusing for an example, but it demonstrates the recursion.
Forget the fibionacci part, focus on recursion. It can be handy sometimes.

[Sicnus]

looking at it, it makes sense but it would make more since if i knew what a Fibonacci was. and that answer=fin(n) or something close to taht, i haven't seen that before, cause i made a program from a sims 24 hour book like that.

[sincka]

Thanx again for the replys guys but I still don't understand how the results are gathered.

offtopic: compile and run that... input idunno 100+ and watch your ram deplete :p

[ 01 August 2001: Message edited by: sincka ]

[kmj]

Here's a very simple example of recursion:


add(int x, int y) {
if (y == 0) {
return x;
}
if (y > 0) {
return add( x + 1, y - 1);
}
if (y < 0) {
return add( x - 1, y + 1);
}
}


Yes, this too is a dumb example, but it's pretty simple.

let's say someone calls add(5,3). Obvoiusly, we know the answer should be 8, right? So let's investigate what happens:

add(5,3): is 3 == 0? no, so call add(5 + 1, 3 - 1)

add(6,2): is 2 == 0? no, so call add(6 + 1, 2 -1)

add(7, 1): is 1 == 0? no, so call add(7 + 1, 2 - 1)

add(8, 0): 0 == 0, return 8

then that 8 gets passed back up the 'call stack' through each recursion of the function, and is finally returned to the code that initially called add.

Obviously, you would never use the above function, but I think it's pretty good for showing how recursion works.


Now, if you understand how fibonacci numbers work (if not, just do a google search), you should see what is being done up there.

[Stuka]

Fibonacci sequence: 1,1,2,3,5,8,13....
or n(x) = n(x-2) + n(x-1) for all x > 2; n(1) = n(2) = 1. And btw, the problem with recursion is the one you found - if the call stack gets too deep, memory goes out the window!

[jemfinch]

Originally posted by Marcel2008:
That's the bug in the listing.
Recursion isn't the best method for calculation fibionacci numbers.


That's not entirely correct. Anything that can be coded iteratively can also be coded recursively. In addition, anything that can be coded iteratively can be coded in the same complexity recursively. Generation of the Nth fibonacci number is an O(n) operation when coded iteratively. The naive recursive implementation, however, is O(2**n) (iirc; the point, however, remains; it's much less effective than the iterative version.) However, a much more clueful recursive implementation, created to take advantage of tail-recursion-optimization in functional languages, is O(n) just like the iterative implementation. Check this (http://www.bagley.org/~doug/shootout/bench/fibo/alt/fibo.ocaml3.ocaml) for an example.

Recursion is a fine way to handle any loop, and is in fact the most general looping construct.

Jeremy

[TheLinuxDuck]

sincka:

If you're still having problems understanding how the function is working, I would suggest (what I do alot) is to write out on paper exactly what the function is doing, from beginning to end.

Start with something like 7, so it's not too complex, then work that number into the equation to see what happens.

By doing it on paper, you force yourself to see everything that happens.. every step.. every number..

Not every one I know does this (or agrees to it's usefulness), but I find it very enlightening.

[sincka]

First of all I want to thank you all for helping me out :)


kmj:
Thank you for the 'simpler' version of recursion. I am now much closer to understanding how it works (well the example of your code is very easy to understand, thanx :))

Oh and to figure out the example posted by me, I will do what TheLinuxDuck suggested.

Thank you all for your help and patience. I'am not home right now. If I have any other troubles about this subject, you will for sure hear from me :D

Thanx again everyone.