Recursion

0 Moh Sam · June 22, 2014
I've been watching bucky's c++ tutorials and found all easy until I got to the recursion thing. I do understand what is recursion but I still can't understand how bucky's code for factorial works after watching it for like 2 hours. I would be grateful if someone offers step-by-step explanation with reference to what is happening.
PS : I understand the code itself but I can't get how it works to get the factorial at the end.
Thanks in advance.
https://www.youtube.com/watch?v=4agL-MQq05E&list=PLAE85DE8440AA6B83&index=31 That's the link to bucky's tutorial if anyone wanna check the code.

Post a Reply

Replies

Oldest  Newest  Rating
+1 Mathias Frits Rørvik · June 23, 2014
Yes, recursion should be avoided if possible. It is more effective to use iteration instead. 
0 Moh Sam · June 22, 2014
Thanks Mathias , I got it now.
+2 Mathias Frits Rørvik · June 22, 2014
It takes 5 and multiplies it by the function call factorial(4), the return value of factorial(4) is 4 * factorial(3). factorial(3) gives 3 * factorial(2). factorial(2) gives 2 * factorial(1). Factorial(1) is a base case so it gives the value of 1.

factorial(1) = 1
factorial(x) = x * factorial(x-1)

This is what happens when you call factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

more clear now?
0 ebelos azuz · June 22, 2014
never mind lol
0 ebelos azuz · June 22, 2014
well you should understand all but the last line of code then...no?   
basically it's like this, the last line does two things.
It multiply 5 by 4 and then it calls the method / function it's in again but instead of x having the value 5 again it now has the value of 4 cos of the x-1 thing.
now that x has the value of 4 when it gets to the code again it will be 4 time 3  and so on till x equals 1 then the if(); will return 1 and c++ just use that as an excuse to unload all the numbers from the multiplying.

int re(int x);

int main(){

    cout<<re(5)<<endl;
}

int re(int x){
    if(x==1){
        return 1;
    }else{
        return x*re(x-1);
    }
}


</re(5)<<endl;
+1 Mathias Frits Rørvik · June 22, 2014
If you don't understand how the factorial function works, you do not understand recursion.

Anyway let's get down to it and see what happens when you call factorialFinder(5)

since 5 is not 1 it returns the following

5 * factorialFinder(4) //since

what is factorialFinder(4) ? Again since 4 is not 1, we get 4 * factorialFinder(3)

Now we have 5 * 4 * factorialFinder(3)

and for the rest:
factorialFinder(3) returns 3 * factorialFinder(2)
factorialFinder(2) returns 2 * factorialFinder(1)
    factorialFinder(1) gives us 1, since we told it to return 1 if x is equal to 1

So when we put it together it we get 5 * 4 * 3 * 2 * 1 


And the result is 120.
0 Moh Sam · June 22, 2014
I don't think I'd like to learn a new programming language unless I'm already done with the previous one (C++ atm).
  • 1

C++

106,932 followers
About

Used in many types of software including music players, video games, and many large scale applications.

Links
Moderators
Bucky Roberts Administrator