Recursion

Image from:

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.

--

--

--

Software Engineer

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Agile Project Management Vs. Traditional Project Management

Jobs you might not think to apply for as a Software Developer

Should We Change the Way We Teach Swift to New Developers?

Going the extra mile with our k8s setup

Kubernetes logo over network of interconnected light nodes

Handling Errors with Profunctor Optics

Kanban Empowered Inventory Management for B2C

3 Things I learned Building My First Bootstrap Theme

Tips for using ESLint in a legacy codebase

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Shaila Nasrin

Shaila Nasrin

Software Engineer

More from Medium

Ancient Algorithms: Recursive Algorithms for Ge’ez Numerals

Memory Management : free()

Binary Exponentiation

AUTONOMOUS VEHICLE