-
Help With Recursion!!!!
Whats the result if N = 5? I dont understand recursion. Can you also show me the steps? Thanks in Advance!
int Fibonacci(int N)
{
if ((N == 1) || (N == 2)) // base cases
return(1);
else // recursive cases
return(Fibonacci(N - 1) + Fibonacci(N - 2));
}
-
What a recursive function does is it calls itself a number of times (obviously). And, you usually put a decrementation or incrementaion or it will be a not ending loop. Then, each function (of the same) does what it has to do and then they all return their value to the root funciton. I know, confusing.
--Garfield
-
Let me guess
You're using Sams Teach Yourself C++ in 21 days??? I had the same problem..................
-
Yeah, ol' Sammy didn't explain it too well.
-
Think of recursive functions as boxes within boxes. Your function was as follows:
Code:
int Fibonacci(int N)
{
if ((N == 1) || (N == 2)) // base cases
return 1;
else
return(Fibonacci(N - 1) + Fibonacci(N - 2));
}
Now, let's say we do the following: "int x = Fibonacci(5);"
What does x equal now?
The best way to diagram program flow of a recursive function, I find, if as a tree:
Code:
Fibonacci(5)
/ \
/ \
/ \
Fibonacci(4) Fibonacci(3)
/ \ / \
/ \ / \
Fibonacci(3) Fibonacci(2) Fibonacci(2) Fibonacci(1)
/ \ | | |
Fibonacci(2) Fibonacci(1) 1 1 1
| |
1 1
In an outline form, that would be this:
Code:
Fibonacci(5) = Fibonacci(4) + Fibonacci(3)
Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
Fibonacci(3) = Fibonacci(2) + Fibonacci(1)
Fibonacci(2) = 1
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = Fibonacci(2) + Fibonacci(1)
Fibonacci(2) = 1
Fibonacci(1) = 1
Hopefully, this helps.
-
Perhaps a different example may help understanding recursion.
Take the faculty function: n!.
Let's calculate 3!, it is: 3 x 2 x 1 = 6.
Let's calculate 5!, it is: 5 x 4 x 3 x 2 x 1 = 120.
As you can see, in general we can calculate n! as:
n! = n x (n-1) x (n - 2) .. x 2 x 1.
In general we start with n and end with 1. So multiplying with 1 is always the final step. The steps between are multiplying with the numbers between n and 1.
int fac (int n)
{
if (n == 1) /* final step is reached */
return 1;
else
return n * fac (n-1);
}
Let's trace this function, it will look like this:
fac (5)
5 * fac (4)
5 * 4 * fac (3)
5 * 4 * 3 * fac (2)
5 * 4 * 3 * fac (1)
5 * 4 * 3 * 1
= 120
-
Hey,
I started Sams Teach Yourself C++ in 21 days...and I too encountered this problem.
After thinking about that function for a few hours, I finally got it :rolleyes: :rolleyes: .....
When I started chapter 7 ( pointers i think ), I found out that the book does not explain the advanced stuff well enough.
Therefore, I stopped reading the book and now I am reading C++ Interactive Course. I found it excellent and even though I'm still in chapter 3, I can already do stuff with classes, arrays, structures, loops etc.
This book keeps building on what you've just learnt. It starts immediately from OOP and builds on it. In this way, you'll never forget what you did back in chapter 1.
I found the Sams book 'explains' a different topic every chapter. I only found the first 6 chapters useful :rolleyes: :rolleyes:
C++ Interactive Course does have some mistakes, but in my opinion, it helps me look at my code and find errors before even compiling.
Well, e-mail me for info about the book :)
Marc