Recursion
--
Most of us know what recursion is and can write recursive code if we are asked to. But when we try to solve advance problems(i.e binary tree, binary search tree etc.) and see recursive solutions, we get confused about how that code is working, so in this post, I will try to explain how a recursive code works behind the scene with a simple factorial finding recursive code, and we will be able to trace more complex recursive code the same way.
Now let’s see the c++ code to return the factorial of a number :
How does this code work?
At first main() function calls the factorial(5), so in the stack at first main() is added and after that at the top of the stack factorial(5) is added.
In the function initially n = 5 then on line 5 it checks if n = 0, as it is not program goes to line 8 and return 5 * factorial(4). So, factorial(4) is added to the stack. Here, 5 * factorial(4) is called from factorial(5), which means whenever factorial(4) will return anything it will return to factorial(5).
Now n = 4 and again on line 5 it checks if n = 0, as it is not program goes to line 8 and return 4* factorial(3). So, factorial(3) is added to the stack.
For n = 3 and again on line 5 it checks if n = 0, as it is not program goes to line 8 and return 3 * factorial(2). So, factorial(2) is added to the stack.
For n = 2 and again on line 5 it checks if n = 0, as it is not program goes to line 8 and return 2 * factorial(1). So, factorial(1) is added to the stack.
For n = 1 and again on line 5 it checks if n = 0, as it is not program goes to line 8 and return 1* factorial(0). So, factorial(0) is added to the stack.
For factorial(0) now on the line 5 it check if n == 0, and this time n is equal to 0, so 1 will be returned to factorial(0). By the way, I didn’t talk about why we have this if(n == 0) statement, this is our base case and every recursive code needs to have a base case so that it is guaranteed the code will stop executing eventually without running out of memory. Now, let's see the stack after 1 is returned to factorial(0).
As 1 is returned to factorial(0), now we have
1 * 1(the value of factorial(0)) -> 1 at the top of the stack. Remember 1 * factorial (0) was called by factorial(1), so the result of 1 * factorial(0)->1 will be returned to factorial(1) and 1 * facctorial(0) will be poped out of stack.
1 is returned to factorial(1), now we have 2 * 1(value of factorial(1)) ->2 at the top of the stack and 2 will be returned to factorial(2) as 2 * factorial(1) was called by factorial(2) and 2 * factorial(1) will be popped out of the stack.
2 is returned to factorial(2), now we have 3 * 2(value of factorial(2)) ->6 at the top of the stack and 6 will be returned to factorial(3) as 3 * factorial(2) was called by factorial(3) and 3 * factorial(2) will be popped out of the stack.
6 is returned to factorial(3), now we have 4 * 6(value of factorial(3)) -> 24 at the top of the stack and 24 will be returned to factorial(4) as 4 * factorial(3) was called by factorial(4) and 4 * factorial(3) will be popped out of the stack.
As 24 is returned to factorial(4), now we have 5* 24(value of factorial(4)) -> 120 at the top of the stack and 120 will be returned to factorial(5) as 5 * factorial(4) was called by factorial(5) and 5 * factorial(4) will be popped out of the stack.
120 will be returned to factorial(5), so we have the result of factorial(5)->120 and this will be at the top of the stack. As factorial(5) was called by main() function, its value 120 will be returned to main() function and factorial(5) will be popped out of the stack.
So, this is how recursion works. If you have found this post helpful, leave a clap, and if there are any mistakes feel free to let me know.
