// Fibonacci series using recursion
// problem from Sams Publishing (example)
// Just in case =Fibonacci series 1,1,2,3,5,8,13,21,34.... (each number after
//the second number is the sum of the two numbers before it
/* in C++ "programming terms" the nth numbers is the sum */
//of n-2 and n-1, as long as n>2
#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));
}
}
/*#########################################*/
OUTPUT
Enter number to find: 6
//for the purpose of this explanation start
// counting lines on the next line
Processing fib(6)... Call fib(4) and fib(5).
Processing fib(4)... Call fib(2) and fib(3).
Processing fib(2)... Return 1!
Processing fib(3)... Call fib(1) and fib(2).
Processing fib(1)... Return 1!
Processing fib(2)... Return 1!
Processing fib(5)... Call fib(3) and fib(4).
Processing fib(3)... Call fib(1) and fib(2).
Processing fib(1)... Return 1!
Processing fib(2)... Return 1!
Processing fib(4)... Call fib(2) and fib(3).
Processing fib(2)... Return 1!
Processing fib(3)... Call fib(1) and fib(2).
Processing fib(1)... Return 1!
Processing fib(2)... Return 1!
8 is the 6th Fibonacci number
My question is this if it returns 1 on line 3 (of output) right in fib(2) why does it keep going to fib(3) on line 4? In other words I understand how the program got up to number 3 I don't know however why it keeps going to line 4, would anybody please care to explain this? Also are recursions used a lot in C++ programming?
UPDATE
After looking over the example I've come to a conclusion and please tell me if I wrong so I can understand this, fib(6) divides in to fib(5) and fib(4), which are started in line 2 and 7 respectably which are in turn divided until each each of the numbers return 1 respectably.
