Recursive functions ( finals!)

[gulu]

I have my CS finals soon and still dont get recursive functions. I answered the question to program the following code and got it right but dont actually know how I arrived there(yes-very embarrassing):

#include <iostream>
using namespace std; 

int factorial(int n );//,int Sn, int x

int main()
{ 
	int n, result, Sn;//x,
	cin>>n;
	result=factorial(n);
	cout<<"n="<<n<<"Sn="<<result;

return 0;
}

int factorial(int n)
{ if(n==0||n==1)
{
return n+1;
}
//Sn=2;
//Sn=(3*Sn)+(n*(Sn-1));
else 

return 3*factorial(n-1)+n*factorial(n-2);//how is this part itirated. WHAT is actually happenning??
}

I don't understand line 25. How is the function actually being called-My instructor didnt really explain this coherently so I'm a little confused-I want to know exactly how, say when you enter 2 as n , that
3*factorial(n-1)+ n*factorial(n-2) would give you 8
Thanx in advance

[untitled]

A recursive function is when you make a function keeps on calling itself in itself to get certain result.

Suppose we put in a 3 in factorial(int n). What will happen? We will have n = 3 in the function factorial.

Now, stick with me a bit. This can be a bit tricky. Think of it as a building. The first time we call a function, we are in first floor of that function. If we call a function once again, we will be in the second floor. Once we finish our business in there, we go back to the first floor. If we also finish business in this floor, we also go back to the previous floor.

Now, let's say the first time we call factorial(int n), we put in 3. Referring to the code above, looks like I have to come down to:

else 
return 3*factorial(n-1)+n*factorial(n-2);

Now, to avoid some confusion, let's make it more clear:

else
return ( (3*factorial(2)) + (3*factorial(1)) );

We have two factorial call in line 25. Now, the program runs and sees that it has to enter the function, so now we go to the 2nd floor with the factorial function. But this time, we have n = 2.

The same thing happens and we hit line 25 once again. So we have to go into the factorial function again, but this time, it's

else
return ( (3*factorial(1)) + (2*factorial(0)) );

So here goes our 3rd floor. In our 3rd time, n = 1, so we hit the if statement and return n+1 which is 2. Now, we're done and we can return a value, so we get back to 2nd floor.

Now, we have the result 2 which comes from n+1 so let's put it in here to make it a bit easier:

else
return ( (3*2) + (2*factorial(0)) );

We still have factorial(0) on the right, so we go to the 3rd floor again with factorial(0) and that yields 1 and we get back down to the 2nd floor, so now we have:

else
return ( (3*2) + (2*1) );

Now, we have the result, so we return to the previous function which is on 1st floor. (3*2) + (2*1) is 8 so let's replace factorial(2) with that.

else
return ( (3*8) + (3*factorial(1)) );

On the first floor, we still have factorial(1), so we go on the 2nd floor with factorial(1). Going through the codes, we go into the if statement because n = 1 and it returns 2 and get back to the first floor, so now let's replace factorial(1) with 2:

else
return ( (3*8) + (3*2) );

Now, we are on the first floor, we can return the result successfully as all the recursive functions have been called. It's like stacking when you call a function in a program.

If you are still confused, tell me and I will see if I can come up with a better example.

[Bazzy]

Article about recursion: http://www.cplusplus.com/forum/articles/2231/

[gulu]

thannx untitled it makes much more sense now but with a teeny little exception- on a certain floor, if we have n=0, n=1 we go up a floor and increment n and this can be with any floor higher than the one we are in? aka the floor 2 and 3 dont hit the if statement unless n= 1 or 0 because you said:

On the first floor, we still have factorial(1), so we go on the 2nd floor with factorial(1). Going through the codes, we go into the if statement because n = 1 and it returns 2 and get back to the first floor, so now let's replace factorial(1) with 2:

so you mean to say ascend to floor higher than the the one currently occupied and apply if statement whether it is second or third floor if (as long as) n=0 or 1 (undertaking that the floor number doesnt have anything to do with how many lines the if statement is above line 25)

[untitled]

Whenever you enter a function, no matter what function, no matter where you are in the program, you go up one floor. When you hit the return statement or the end of the function, you go down one floor.

[Corpus]

Hi gulu

The other posts notwithstanding, here's a little more on recursion.

Generally, you make a decision whether to solve a problem recursively or not from whether or not you can solve the problem by solving a smaller version of the problem itself. As an example, the old factorial

n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1

is a prime candidate for recursive solutions since the problem "find n!" can be found by solving a small version of the problem, i.e. "find (n-1)!". To see this, we re-write the above equation:

n! = n * (n-1) * (n-2) * ... * 3 * 2 * 1
    = n * [(n-1) * (n-2) * ... * 3 * 2 * 1]
    = n * (n-1)!

Hence, we can find n! by finding (n-1)!

Okay. This is the point where most of your assignments start - the teacher has already told you that a recursive solution exists, so now we need to express it.

Recursive solutions consist of two cases: The recursive case (RC) and the base case (BC)

The BC is where the problem is sufficiently simple to be solved without recursion, e.g. factorial with n=1, where we know that 1! = 1. In this case we do not need recursion to solve our problem.

The RC is where we solve a problem by solving a smaller version of the problem itself, e.g. factorial for n>1 where n! = n*(n-1)!.

Now, the recursive solution recipe:

(1) State the problem to yourself. Use terms that can be used to define the problem size. E.g. "Find n! = n*(n-1)*...*3*2*1" (here, 'n' is the problem size)

(2) Find the BC. The "simple" version of the problem where recursion is not necessary to solve it. Example: Factorial: BC is n=1 or n=0 , where n! = 1

(3) Find the RC and make sure that the RC converges on the BC, i.e. that the problem does indeed get smaller all the time. Example: RC is n>1 where n! = n*(n-1)!. (n-1)! is indeed a smaller problem than n!

(4) Ensure (prove) that the RC will eventually hit the BC. Example: Factorial RC is n>1 in which case n decreases by 1 for each recursive call. Since n>1 and n decreases by 1 every time, n will eventually be 1, the BC

By first finding out that a recursive solution exists and then following the recipe (1)-(4) above, recursion becomes much easier...with training.

Here is the (pseudo) code for factorial:

// Find n! = n* (n-1) * ... * 3 * 2 * 1
int fac(int n)
{
  if(n==1 || n==0) return 1; // BC (n=1 or n=0) using definition of n!
  else return n*fac(n-1); // RC (n>1)  n! = n* (n-1)!
}

Hope this helps - good luck!

[gulu]

Again thanx for all the posts I understand the concepts better now