Recursion

Recursion can be used when you have a big problem that can be divided into smaller sub problems and by solving those sub problems we can  solve the bigger problem. For example, how we find out factorial of, we calculate like this:

                                                           

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

If we see the line above we are multiplying  n*(n-1)*(n-2)*...*1, so if we were finding out (n-1)!.

 How would we write it?

 We would write it like :

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

Now, we can write the first equation n! = n * (n-1)!

Similarly, (n-1)!= (n-1)*(n-2)!

So, finding out factorial of n is dependent on finding out factorial of n-1 and finding factorial of n-1 is dependent on finding out factorial of n-2. That's why we can use recursion here, because here we have  sub problems with same nature but smaller input size.

Now if we see the c++ code for it:

In the code, in main function I have called the function factorial(5). So, main is asking the factorial function for the answer of n!, in the function initially n = 5 then in line 6 it checks if n=0 , as it is not program goes to line 10 and return n*factorial(n-1) that means 5*factorial(4) so, again factorial()

function is called and the is another instance of the factorial function is created which has n=4. After this for n=4 factorial(4) is called and it goes on like this.

By the way I didn't explain why I have written a if condition in the beginning of  the function that is written because in recursion you need a base case and if you don't give a base case after factorial(0) it will call factorial(-1) then factorial(-2) and so on...but as we are making instance of functions, it is occupying some memory and if we keep calling the function we may run out of memory and we will get segmentation fault. The other reason of giving a base case is we want to eventually come up with an answer and we have to make sure recursion stops somewhere,and as we know 0!=1 we are stopping there . 

Now lets go back to the code and see how the function calling is happening :

So, the function is called till n=0 and factorial(0) is called. And the instances of the function that means factorial(5),factorial(4), factorial(3),factorial(2) , factorial(1) is still waiting in line 10 to get the values of  factorial(4), factorial(3),factorial(2) , factorial(1) and  factorial(0). When n becomes 0 the the if condition is satisfied and 1 is returned. Keep that in mind that 1 is returned to factorial(1) and not to main(). So, now factorial(0) = 1 and as we return n*factorial(n-1) that means factorial(1) = 1*factorial(0) = 1*1=1. This 1 is returned to factorial(2) so,factorial(2) = 2*1=2 which is returned to factorial(3) so,factorial(3) = 3*2=6 .

 This 6 is returned to factorial(4) so factorial(4) = 4*factorial(3) = 4*6 = 24. This 24 is returned to factorial(5) so factorial(5) = 5*factorial(4) = 5*24 = 120. Finally 120 is returned to main() function and it is printed. You should run the code and see ;). 

This is how the  code is working. And in the memory these functions are stacked like this:

I hope it helped you understand how recursion works.