Doubts with recursive Fibonacci

I don't understand how C/C++ works when there is a sum on the recu

Page 1 of 1

3 Replies - 1324 Views - Last Post: 03 February 2009 - 10:50 AM Rate Topic: -----

#1 ingombs  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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 );
}



thanks in advance,

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  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • 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.
Was This Post Helpful? 1
  • +
  • -

#3 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • 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.

Here is a version of your function where I added in some debugging lines to help you see the function call stack:
/**
 * 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

Was This Post Helpful? 1
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2255
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1