CODEWITHSUNDEEP
c++functionrecursionreturn
user2580684
user2580684

Reputation: 27

Difficulties in understanding this recursion

I don't get this recursion exercise in C++. Here it is:

int fatt(int x){
    int s=1; // here. since 's' will always be 1 shouldn't i get 1 as an output???
    if(x>1) { s = x*fatt(x-1); }
    return s;
}

int main()
{
    int n;
    cout << "Type a number: ";
    cin >> n;
    if (n < 0) { cout << "Error" << endl; }
    if (n <=1) { cout << "Factorial: 1" << endl; }
    else { cout << "Factorial: " << fatt(n) << endl; }
}

If I put s=0 it returns me as an output always 0, if I put 2 it doubles the result O.o I don't get how it works. I understand that x is always getting diminished until reaches 2 and the returns the result but everytime the function is called shouldn't 's' be given the value of 1???

Upvotes: 0

Views: 114

Answers (3)

Twahanz
Twahanz

Reputation: 224

's' should be 1 but it gets assigned and then changes the value it holds upon the completion of a function.

Recursions can be a bit hard to understand at first but once you do, it's beautiful.

I suggest you use a pen and paper.

1) Let x = 3;

int fatt(3) {
    int s = 1;
    if (3 > 1) s = 3 * fatt(3 - 1);
    return s;}

2) In the function 3>1 = true so it gets passed on again but this time as (3-1) i.e 2

Note: function isn't done executing

3) Now x = 2

int fatt(2) {
    int s = 1;
    if (2 > 1) s = 2 * fatt(2 - 1);
    return s;}

4) Repeat step 2) (2-1) i.e 1

5) Since x IS NOT > 1 in the 3rd function call this results in the returning of s

s = 1;
return s;

So...

Starting at the 2rd function call: 

s = x * fatt(x-1);
s = 2 * 1;
return s;

Repeat this again for the first call)

s = x * fatt(x-1);
s = 3 * 2;
return s;

Think of it like a stack of functions

1st stack ------- calls stack 2 and waits

2nd stack ---------- calls stack 3 and waits

1st stack ---------- waiting

Finally...

3rd stack ---------- condition not met return

2nd stack ---------- condition done return

1st stack --------- condition done return

Hope that helps

Upvotes: 0

Smeeheey
Smeeheey

Reputation: 10316

The variable s is local to the given instantiation of the function fatt. As the function recursively calls itself, every invocation gets its own new copy of s. This is initialised to 1, but doesn't affect all the previous s instances lower down in the stack. Each one of those is then assigned to the result of the fatt invocation mediately after it multiplied by its local copy of x.

Upvotes: 1

Tommy Andersen
Tommy Andersen

Reputation: 7220

Say you call the function with the parameter value 3: It would look like this:

int fatt(3) {
    int s = 1;
    if (3 > 1) s = 3 * fatt(3 - 1);
    return s;
}

So s is the result of the calulation 3 * fatt(2) and the result of fatt(2) is:

int fatt(2) {
    int s = 1;
    if (2 > 1) s = 2 * fatt(2 - 1);
    return s;
}

So s is the result of the calculations 2 * fatt(1) and the result of fatt(1) is:

int fatt(1) {
    int s = 1;
    if (1 > 1) s = 1 * fatt(1 - 1);  // False so this is never executed.
    return s;
}

The result of fatt(1) is 1. So that is what we return to the call of fatt(2) which then translates to:

s = 2 * 1;

Which gives the result 2 which is then returned to the call of fatt(3) which then gives:

s = 3 * 2;

Which gives the result 6.

Remember that the local variable s is pushed on the stack each time the function is executed. So it is not the same variable.

If you initiated s to 2, then the first line would read: s = 2 * 2; and the rest of the function would give double the value in result. Since s is really a factor that you end up multiplying with, in your factorial:

So the sequence: 3 * 2 * 1 becomes 3 * 2 * 2.

Upvotes: 3

Related Questions