What is Recursion?
Recursion in programming, is the process in which a function being executed calls itself using it’s function call. Such a function is called a recursive function. Recursion is used to solve complex mathematical problems. It has the advantage of being able to solve them faster while using a lesser number of lines of code.
There are 2 components found generally in all recursion examples. The base case and a reduction step. The base case is what causes the recursive function function to terminate. The reduction step (sometimes referred to as recursive step) breaks down a larger problem into many smaller problems. See the example down below for further explanation.
There is sometimes a third component, called the general case, which is basically any condition that is not the base case.
Recursion example
In this example the line, if n == 1 is the base case and elif n > 0 is the general case. n == 1 is the condition that has to be met for the recursion function to terminate. Without this, we would end up in a never ending cycle. Furthermore, the reduction step here is factorial(n-1). The reduction step breaks down the task of finding the factorial to smaller tasks of finding n-1.
def factorial(n):
if n == 1:
return n
elif n > 0:
return n * factorial(n-1)
print(factorial(5))
This code is too small and simple, but in problems where recursion is used in the real world, you’ll find that a non-recursive solution takes longer to code and uses many more lines.
Memory Allocation
When a recursive calls itself over and over again, it is allocated memory in a place called the “stack”. It’s called stack, because each time the function is called it “stacks” onto the previous.
Stacks follow the L.I.F.O rule, which stands for “Last In First Out”. The concept is that the ones at the bottom of the stack are the ones that first entered the stack. Hence, they will also be the last to leave the stack. The one’s on the top however, will be the first to leave. Remember, when removing items from a stack, you remove them starting from the top, not the bottom.
Understanding how the stack works is vital to understanding the complete behavior of recursive functions.
Stack Overflow Problem
If the base case condition is not met, a recursive function will cause a Stack Overflow error, or an “Infinite Loop” problem. Consider the following code.
def factorial(n):
if n == 1:
return n
elif n > 0:
return n * factorial(n)
print(factorial(5))
As you can see, the base condition, n = 5 is never met since the value of n never decrements. Because of this the loops continues forever until it floods the memory causing a Stack Overflow error. Some IDE’s like Visual Studio will detect an error like this coming and terminate the process themselves after a certain number of recursion calls.
Sometimes programming languages have functions that can set a limit to the number of recursive calls. This helps avoid any Stack Overflow Errors. An example of this is the sys library in Python.
Tower of Hanoi
Along with factorials, the Tower of Hanoi problem is frequently associated with the use of recursion in programming. We won’t be explaining this code here however. Try running the code for yourself, tampering with it. If you understood the above concepts, you should be able to understand this as well.
This marks the end of our Recursion in Programming Guide.