Hey there! Hope you are doing well. In this article, I am going to cover
- What is recursion,
- How memory is allocated for recursion
- When we should use recursion ( over iteration )
- It’s limitations ( or when not to use )
- Reference Articles.
What is Recursion?
So let’s start with a real world example. A simple yet exciting illustration is Googling Recursion. Noticed what happens?
It keeps asking you "Did you mean Recursion?" And even after clicking it, it continues to prompt the same question. Doesn’t it appear to be calling itself over and over again? Well, that is recursion in play.
In simple words, Recursion is the process where a function calls itself directly or indirectly.
def counting(no):
print(no)
counting(no+1)
When does recursion stop?
As you have already noticed, in the above example, the recursion goes infinitely. With this, our terminal will overflow with prints and the program’s call stack might crash with Stack overflow, where it will be no longer able to track any further function calls.
So how do we stop it? We use a simple base case from where the function returns with a terminal point and does not call itself any further.
def counting (no):
if no==10:
print("Recursion ends at 10")
else:
print(no)
counting(no+1)
In the above code, when our recursion hits an input with no=10, it simply prints the statement and no longer calls itself again. Thus, we do not have any stack overflow this time.
Doesn’t it sound similar to iteration?
Well, it does. Like iteration (irrespective of ‘for’ or ‘while’ loop), in recursion also, we perform sub-tasks repetitively. So broadly speaking, we can implement every logic of recursion with iteration if we want and vice versa.
Then why recursion?
Even though it looks similar, recursion has certain advantages over iteration on the basis of readability of code.
Specially when we need to maintain a stack to keep track of processes we are calling so that they can be referenced again at later point of time. Unlike in iteration, recursion keeps a memory call stack implicitly for its execution.
How Recursion works?
As said, Recursion works with the help of Memory Call stack.
In other words, when any function gets called, some memory is allocated for storing its data so that it can be referenced when required. This memory does not get freed up until the function has returned its control or exited from the function’s reference.
Now when other functions get called successively, those calls get stacked in the memory as well, until its execution is completed one by one in LIFO (Last In First Out) sequence.
The same process takes place when recursion happens. All the function calls get stacked in the memory until they are executed. Once a function returns its control, the stack is popped and next function call in the stack is being executed.
Let’s analyse with a code snippet:
def counting(no):
if no>5:
return
counting(no+1)
print(no, end = " ")
counting(0)
The output of the code snippet will look like: 5 4 3 2 1 0
Why the output is in reverse order?
If we run in debug mode and watch the call stack, we will find something like:
Decoding Call stack:
As we can see, the call stack started with the function call at line
no. 9. This is the entry point of our recursive function andcounting(0)gets pushed.Post that, every time we were calling
counting(no+1), from lineno. 6, we have an entry of it in the call stack with the corresponding value. Print statement never gets executed since before that only Function invokes itself recursively.Once we reach the base case that is,
no>5, we return from the function for the first time. Hence the last function call that got pushed withno=6gets popped out of the stack.Hereafter, popping from the call stack begins. Memory points the next function in the call stack and execute the remaining statements in the function which previously weren’t executed.
In this case,
print(no)gets executed and5gets printed in the terminal.Similarly, all successive functions get popped out of the call stack one by one in LIFO manner and the print statement is executed with the corresponding values of no .Hence
4 3 2 1 0gets printed.
And that’s it.
When to use it?
From the above code examples, it can be seen that the same task of printing number is getting repeated as the function keeps calling itself with a different parameter.
In other words, we can find the use of recursion where
- We have a definite subtask to be performed.
- We want to repeat that subtask over and over again.
- We need a stack to keep track of processes so that can be referenced later.
For example, to implement traversing trees, recursion would be a better choice.
When not to use it?
Even with this tempting advantage of recursion (who does not like readable code? 👀) , Recursion has certain disadvantages. As we have already seen, recursion requires more memory usage since it saves each function calls in the implicit stack. This can be a major overhead when a task is simpler. In those cases, iteration should be the better choice.
For example, to implement fibonacci series iteration would be a better option than recursion.
References:
Conclusion:
I hope this article helps you to get started with the basic concepts of Recursion.
In the upcoming articles, I am going to cover recursion in more depth like how it works internally, how each operation is handled in recursive functions, more advance example and its complexity with optimisation techniques like dynamic programming.
For such updates and articles on Data structure and algorithm, follow this page and keep supporting. Cheers! 🥂
Top comments (1)
It's totally possible to write recursive functions without any stack overflow issues using 'trampolining'