Recursions Second Time around

[incognito]

Ok, my second time around with this same problem.....now I understand the actually recursion, what it's doing and stuff but not the theory behind it.

Take this for example

// Fibonacci series using recursion
#include <iostream>

int fib (int n);

int main()
{

	int n, answer;
	std::cout << "Enter number to find: ";
	std::cin >> n;

	std::cout << "\n\n";

	answer = fib(n);

	std::cout << answer << " is the " << n;
		std::cout << "th Fibonacci number\n";
	return 0;
}

int fib (int n)
{
	std::cout << "Processing fib(" << n << ")... ";

	if (n < 3 )
	{
		std::cout << "Return 1!\n";
		return (1);
	}
	else
	{
		std::cout << "Call fib(" << n-2 << ") ";
			std::cout << "and fib(" << n-1 << ").\n";
		return( fib(n-2) + fib(n-1));
	}
}

From Sams Teach Yourself C++ in 21 days by Jesse Liberty

Now that we got that over with.........it says that the nth number is equals to the sum of the two previous numbers or nth=n-1+n-2;

right?


Now the Theory behind this.....why must we dig down to the last two numbers 1,1 the first two numbers to add their return values in order to get the nth number, and not just do

result=n-1+n-2 I know this is wrong for the most part Because if you do it with the number 6 it doesn't work since you get 5+4=9 and not 8 like it is........


Thank you in advance, if you don't understand my question please tell me.

[MrWizard]

It sounds like you answered your own question. Simply adding the number - 1 and -2 will simply not work as you disproved with your case.

Consider the Fib. Seq.

0,1,1,2,3,5,8,13...

Its obvious to see starting at the beginning that is how the new numbers are generated ( (n - 1) + (n - 2) ). Maybe I don't understand what you are asking. Given an index of course it has to start at the beginning in order to work its way back.

This probably didn't help

[incognito]

Well I understand Recursions, just don't understand the logic behind finding the Fib series with Recursions, recursions themselves I get it, not the logic used to solve this problem.

[JamesMI]

The Fib. Seq. is defined as...
 f(1)=1
 f(2)=1
 f(n)=f(n-1)+f(n-2)  

so for example, the first 5 terms are...

f(1) = 1  //by definition
f(2) = 2  //by definition
f(3) = f(n-1) + f(n-2) = f(3-1) + f(3-2) = f(2)+f(1) = 1 + 1 = 2
f(4) = f(n-1) + f(n-2) = f(4-1) + f(4-2) = f(3)+f(2) = 2 + 1 = 3
f(5) = f(n-1) + f(n-2) = f(5-1) + f(5-2) = f(4)+f(3) = 3 + 2 = 5

so in order to find f(5) in other words...
  f(5) = f(4)+f(3)

but, f(4) = f(3)+f(2) and f(3) = f(2)+f(1)
so we get
  f(5) = f(3)+f(2) + f(2)+f(1)

but, f(3) = f(2) + f(1)
so we get
  f(5) = f(2)+f(1) + f(2) + f(2)+f(1)

but by definition f(2) = 1 and f(1) = 1
so we get
  f(5) =   1 +  1  + 1 + 1 +  1
       = 5

The fib. seq. is defined using recursion. In order to find f(n)
you have to call the function itself at least twice. Once for
f(n-1) and once for f(n-2). Unless of course n<3.

In the example above in order to find f(5) you have to find
f(4),f(3),f(2), and f(1) first. What I tried to show in the example
is that you can break any term in a fib. seq. down to terms of f(1)
and f(2).

Im not sure if this is what you meant by theory, but I hope it helps.
James