Recursive Fibonacci

[antirsi96]

I am learning recursive functions at the moment and i am really confused.

Could someone explain how does the fib-1 and fib-2 variables take the numbers before them and do not extract 1, respectively 2 from themselves. Does this has to do with the stack memory? Is fib-1 like an array member here(ex arr[i-1])?

Here's the code! Thank you!

#include <iostream>
using namespace std;

int fibonacci(int fib)
{
	if(fib==0)
		return 0;
	if(fib==1||fib==2){
		return 1;
	}
	else{
		return fibonacci(fib-1)+fibonacci(fib-2);
	}
}

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cout<<fibonacci(i)<<" ";
	}
	return 0;
}

[Smac89]

I don't understand your question, but there is one thing that can make your code run faster. If you directly compute fibonacci(n) and store the results into an array, you now have O(1) access to fibonacci(1..n). So rather than computing fibonacci 1 to n, you first calculate fibonacci n. Then as the calculation is growing, you store the results of each recursive call into an array. In the end you have all the fibonacci numbers stored in an array, then you simply print each one with a for-loop. This is one form of memoization when it comes to computing fibonacci numbers

[antirsi96]

I mean, why don't fib-1 and fib-2 do not extract 1 and 2 from them. Why are they pointing to the numbers before them? for example if fib is 8 then why is fib-1==5(and not 8-1= 7) and why is fib-2==3(and not 8-2=6)?

[MaxterTheTurtle]

I'm not sure I see your problem. I rewrote the code to be a bit clearer.

#include <iostream>

int fibonacci(int fib)
{
	if (fib == 0) {
		return 0;
	}
	
	if ((fib == 1) || (fib == 2)) {
		return 1;
	}
	
	return (fibonacci(fib-1)+fibonacci(fib-2));
}

int main(void)
{
	/* declare an integer */
	int n = 0;
	
	/* get data from user */
	std::cin >> n;
	
	std::cout << std::endl;
	
	/* loop through input */
	for (int i = 0; i <= n; i++)
	{
		std::cout << fibonacci(i) << std::endl;
	}
	
	std::cin.sync();
	
	/* pause the console */
	std::cin.get();
	
	return 0;
}

If I input 4, I get the results 0 1 1 2 3. This makes sense to me.

fibonacci(0) = 0; /* hits return statement */
fibonacci(1) = 1; /* hits second return statement */
fibonacci(2) = 1; /* hits second return statement */
fibonacci(3) = fibonacci(3 - 1) + fibonacci(3 - 2);	/* return 2 */
		      /* returns 1 */     /* returns 1 */
fibonacci(4) = fibonacci(4 - 1) + fibonacci(4 - 2);
			fibonacci(3 - 1) + fibonacci( 3 - 2) + fibonacci(2 - 1) + fibonacci(2 - 2)
			fibonacci(2 - 1) + 1 + 1 + 0;
			1 + 1 + 1 + 0;
			= 3;

Dang, that was longer than I expected. I'm not sure about fibonacci numbers, but that is how the function acts.

[Smac89]

Ok I think I sort of understand what you are asking. You were looking at the output of the function as the recursion unwinds. I modified your code to print the output at each function call and here is what I get with fibonacci(5).

5
4
3
2
1
2
3
2
1

The 5th fibonacci number is 5

#include <iostream>
using namespace std;

int fibonacci(const int fib)
{
	cout << fib << endl;
	if(fib==0) return 0;
	else if(fib < 3) return 1;
	else return fibonacci(fib-1)+fibonacci(fib-2);
}

int main()
{
	cout<<"\nThe 5th fibonacci number is " << fibonacci(5) << endl;
	return 0;
}

This is perfectly normal output of the function when using the basic recursion method for computing fibonacci. This is because each recursive call is trying to compute fib-1 and there is no way for it to remember what it had recently computed. For example in the output above, we try to compute fibonacci 5. I will now follow the recursive calls to show that the above output is what is expected.

fibonacci(5)
--->5
fibonacci(5 - 1)
--->4
fibonacci(4 - 1)
--->3
fibonacci(3 - 1)
--->2
[return 1]
1 + fibonacci(3 - 2)
--->1
[return 1 + 1]
2 + fibonacci(4 - 2)
--->2
[return 2 + 1]
3 + fibonacci(5 - 2)
--->3
3 + fibonacci(3 - 1)
--->2
[return 3 + 1]
4 + fibonacci(3 - 2)
--->1
[return 4 + 1]

--->The 5th fibonacci number is 5

As you can see from the output trace, there are times when the code is computing something it has previously computed [ex. fibonacci(3 -1)]. This is wasteful because it is slow and takes precious computation time. There is one way to help the function remember the previous computation and this is by using an array.

Here is a DP method for computing fibonacci:

#include <iostream>
using namespace std;

static int fib_helper[100] = {0};

int fibonacci(const int fib)
{
	cout << fib << endl;
	if(fib < 3) return fib_helper[fib];
	fib_helper[fib] = fibonacci(fib - 1) + fib_helper[fib - 2];
	return fib_helper[fib];
}

// test program
int main()
{
	fib_helper[1] = fib_helper[2] = 1;
	cout<<"\nThe 5th fibonacci number is " << fibonacci(5) << endl;
	return 0;
}

Output:

5
4
3
2

The 5th fibonacci number is 5

Now I will follow the recursive calls:

fibonacci(5)
--->5
fib[5] = fibonacci(5 - 1) + fib[3]
--->4
fib[4] = fibonacci(4 - 1) + fib[2]
--->3
fib[3] = fibonacci(3 - 1) + fib[1]
--->2
[return fib[2]]
fib[3] = 1 + 1
[return fib[3]]
fib[4] = 2 + 1
[return fib[4]]
fib[5] = 3 + 2
[return fib[5]]

The 5th fibonacci number is 5

Watch this vid to understand how the second method works:
http://www.youtube.com/watch?v=OQ5jsbhAv_M

With the way the function is used now, each call to fibonacci(n) will run in linear time. i.e. everytime you call it, it will compute:

fibonacci(n)
fibonacci(n - 1)
fibonacci(n - 2)
....
fibonacci(n - (n - 2))

// test program
int main()
{
	fib_helper[1] = fib_helper[2] = 1;
	cout<<"\nThe 5th fibonacci number is " << fibonacci(5) << endl;
	cout<<"\nThe 6th fibonacci number is " << fibonacci(6) << endl;
	return 0;
}

5
4
3
2

The 5th fibonacci number is 5
6
5
4
3
2

The 6th fibonacci number is 8

This is still good in comparison to it's previous exponential run time. But with the knowledge we now have with the DP method, this seems like more wasteful computation power since we already have the results of previous computations in the array, so there is still room for optimization of the program and here it is:

int fibonacci(const int fib)
{
	cout << fib << endl;
	if(fib < 3 || fib_helper[fib] > 0) return fib_helper[fib];
	fib_helper[fib] = fibonacci(fib - 1) + fib_helper[fib - 2];
	return fib_helper[fib];
}

Now notice the output:

5
4
3
2

The 5th fibonacci number is 5
6
5

The 6th fibonacci number is 8

[antirsi96]

I got it know! I knew the algorithm was good, but i just couldn't figure out how it works. Now it all makes sense! Thank You Smac89!