# Doubts with recursive Fibonacci

Page 1 of 1

## 3 Replies - 1392 Views - Last Post: 03 February 2009 - 10:50 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=84387&amp;s=dc2c6af86eccb0fe7bd366180054e361&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ingombs

Reputation: 0
• Posts: 1
• Joined: 03-February 09

# Doubts with recursive Fibonacci

Posted 03 February 2009 - 09:01 AM

Hi all! My question is about fibonacci with recursion. I understand the math behind that, my problem is about C/C++ , the first if says that in case n==0 or n==1 , return n , I think that "return n" must exit the function and return to the main function following the if statement. For example,
case n = 4 the values follows like that n = 4 when n enter the function, n=3 after the first recursion call, and follow to 2, 1, 0, 1, 2, 1, 0
Fibonacci(4) = 3
And now my doubt, n becomes 1 after the third recursion call, why it continues in the function? If in the else block I cut the fibonacci( n - 2 ), like return fibonacci( n - 1); the recursion stops when n=1, but with a sum like fibonacci( n - 1 ) + fibonacci( n - 2 ); the recursion continues if n=1 or 0 .

```unsigned long fibonacci( unsigned long n )
{
if ( n == 0 || n == 1 )  // base case
return n;
else					 // recursive case
return fibonacci( n - 1 ) + fibonacci( n - 2 );
}

```

Ingo Sousa

This post has been edited by ingombs: 03 February 2009 - 09:16 AM

Is This A Good Question/Topic? 0

## Replies To: Doubts with recursive Fibonacci

### #2 Gloin

• Expert Schmexpert...

Reputation: 235
• Posts: 4,489
• Joined: 04-August 08

## Re: Doubts with recursive Fibonacci

Posted 03 February 2009 - 09:16 AM

Quote

And now my doubt, n becomes 1 after the third recursion call, why it continues in the function?

I'm not sure I understand your question but about the above, it doesn't.

when the function is called with fib(2) then the function first evaluates n == 1 || n == 0 (false, false) so it continues
next it calls itself,
return fibonacci( n - 1 ) + fibonacci( n - 2 );
which creates 2 new function calls, both will result in the return of 1 and 0 respectively and there will be no further recursive calls from these branches.

### #3 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: Doubts with recursive Fibonacci

Posted 03 February 2009 - 09:57 AM

Recursion works by calling a function (from within itself) multiple times and returning values for each call.

For example:
``` int sum(int n) {
if (n == 1) return 1; else return sum(n-1) + n;
}
```

In this simple little function we take a number n=4 and we call sum(4). That function calls sum(3) which calls sum(2) which calls sum(1) which RETURNS 1, which causes sum(2) to return 3, which causes sum(3) to return 5 which causes sum(4) to return 10. So 1+2+3+4=10

So first the recursion dives down, and then it comes back up.

So in your fibonacci() function (shortened to fib() for this) when you call fib(4) it calls fib(3), fib(2), fib(1) which returns 1, then fib(2) calls fib(0) (the fib(n-2) part) which return 0, so fib(2) returns 1+0=1

So fib(3) now calls its second function (fib(n-2)) and we get fib(1) which returns 1 so fib(3) returns 1+1=2

So fib(4) now calls its second function fib(2) which returns fib(1)+fib(0) which is 1, so fib(4)=2+1=3

So
fib(5)
= fib(4) + fib(3)
= (fib(3) + fib(2)) + (fib(2) + fib(1))
= ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
= (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
= 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
= 5

So ... the return statement returns the value for the CURRENT function call and that value gets used by the parent call.

so when fib(2) calls fib(1) and fib(1) return 1, then that values is used in the current calculation going on in fib(2)... so
fib(n-1) + fib(n-2) first gets the value of fib(n-1) once that is returned then it gets the value of fib(n-2) once it has that value it adds the two together and returns the result.

```/**
* Fibonacci example -- will print out a visual representation of the function calls.
* The constant FIBNUMBER is the fibonacci number we want to see calculated.
*/
#include <iostream>

// Change the value of FIBNUMBER to see a different calculation
#define FIBNUMBER 4

//I added the argument m to keep track of the parent function.
unsigned long fibonacci( unsigned long n, unsigned long m = 999 )
{
//These fist few lines print out the debugging information:
//  Print out spaces to show how deep our function call is...
for(int c = FIBNUMBER+1 - m; c> 0; c--) { std::cout << "  "; }
std::cout << "fibonacci(" << n << ") called";
if (m!=999) {  //If the function is called from another function...
std::cout << " from fibonacci(" << m << ")\n";
} else {
std::cout << std::endl;
}

//Since we want to capture the returning values I changed the logic here a bit
// to use a common return statement rather than 2. retValue holds the value
// that we will return so that we can print out some information before exiting
// this instance of the function.
unsigned long retValue;
if ( n == 0 || n == 1 )  {// base case
retValue = n;
} else  {					// recursive case
retValue = fibonacci( n - 1, n ) + fibonacci( n - 2, n );
}

//Print out the return info...
for(int c = FIBNUMBER+1 - m; c> 0; c--) { std::cout << "  "; }
std::cout << "fibonacci(" << n << ") returns: " << retValue << "\n";

// return the value
return retValue;
}

int main()
{
fibonacci(FIBNUMBER);
system("pause");
return 0;
}
```

This post has been edited by NickDMax: 03 February 2009 - 10:56 AM

### #4 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: Doubts with recursive Fibonacci

Posted 03 February 2009 - 10:50 AM

I fixed a typo in the above program. The printed return value should not be n but retValue.