Understand the process of using recursion in Python. Simplify your code and make it more readable with recursion.
What is recursion?
Recursion is when the method of solving a problem contains that same method in smaller chunks. In nature, recursion is brilliantly displayed all around and inside us. To have a visual example of this, think of a Romanesco broccoli or a snowflake. Zooming in on these objects, one would find that each part is repeatedly composed of smaller self-similar patterns, up to the very smallest part of it. Applying this fascinating technique in programming would mean having a solution built in such a way to repeatedly shrink a problem into smaller simpler sub-problems of itself, until it can be shrunk no more. The result would be the combination of all the results of sub-problems together.
In recursion there are two important parts that one should keep in mind:
- Base case
This is what stops the recursive process. It is vital in any implemented recursive function, as otherwise it will never terminate. It is translated to the smallest possible sub-problem that will be encountered and solved, after iterating through all the smaller cases of that same problem.
- Reduction step
The recurring step which forces the current problem to a smaller version of itself. This step will be called a number of times, each time moving closer to the base case.
Why use recursion?
Recursion is one way of solving particular problems, but it is not the only way. Different programming languages and programming paradigms process it differently. So one needs to take these into consideration when understanding whether to implement a function recursively or not. The following are some pros and cons when it comes to recursion.
| Advantages | Disadvantages |
| Avoids nested loops | Usually slower |
| Reduces time needed to write code | Less memory-efficient as there is danger of
running out of stack space |
| There are cases where it reduces
time-complexity |
Can be relatively confusing to think with its logic |
Implementing recursive functions in Python
To demonstrate recursion, an example will be shown using both the iteration method and using normal recursion. Let us imagine we need a function to calculate the power of a number. In Python this can be easily done using ** operator, however we will be implementing our own way how to do it to demonstrate recursion.
First code snippet shows how to do this without using recursion:
def power_iteration(base, power):
res = 1
for num in range(power):
res=res*base
return res
print(power_iteration(6,4))This method is using a loop, repeatedly storing the result in a variable until the base number has been multiplied by itself for the power number provided. As can be noticed, the power_iteration function is not calling itself so there is no recursion involved here.
The code snippet below does the same thing, this time using recursion.
def power_recursion(base, power):
if power == 0: # Base Case
return 1
if power >= 1:
return base * power_recursion(base, power - 1) # Reduction Step
print(power_recursion(6,4))Let’s break this down using the parts mentioned earlier:
Base case:
The smallest problem encountered when finding the power of a number is x^0 =1 i.e that number to the power of 0, which will give a 1. So a check is made to understand if the current power in the calling is 0 and, if this is the case, a 1 is returned.
Reduction step:
To break down the problem in smaller ones and move the function towards the base case mentioned above, we need to constantly decrease the power number by 1 moving towards the base case above.
In normal recursion, each call to the power_recursion function adds a stack frame to the call stack in memory. Looking at the below stack frame, starting from the bottom and following the orange arrow upwards, we can see how each function call is put on the call stack. Once the base case Is reached, it returns a 1 and the frames are now popped in reverse order, each time using the returned value of the previous result. This continues on until the last result is returned.
Python and Tail Call Optimisation
The above example is designed using normal recursion. It is interesting to note that due to having to reserve a separate stack frame for each call, a stack overflow might occur. To avoid this, functions can be designed using tail recursion. With tail recursion, the design will be in such a way that there will be no need to stay popping the stack (the path marked in blue in the figure above) to get to the final result. In tail recursion, the final result would be immediately available with the last invocation of the method.
Some programming languages differentiate between normal and tall recursion and make use of the latter technique for optimisation. This is what we call tail call optimisation. Python, however, does not make use of this tail call optimisation, meaning that normal and tail recursion are treated the same. This means that there is more chance of having a recursion depth error.
To avoid this stack overflow with recursion in Python, a recursion limit Is automatically set. However one has the option to increase this if necessary. it can be set using a function in sys library setrecursionlimit(). For example: sys.setrecursionlimit(10**7).
Conclusion
This was a quick overview on how to implement recursion in Python. One must always keep in mind that different problems can have different solutions and implementations. Recursion is one way how some problems can be tackled. It can be quite an elegant and efficient solution if used appropriately, but it is important to evaluate whether it is suitable in the situation in terms of time complexity and speed.
