In short, recursion is not bad in Python and is often needed for programs that will be doing depth first traversals like web crawlers or directory searches. The Towers of Hanoi smallest steps problem can also be solved using a recursive algorithm with the following Python code.
def hanoi(num_disks):
if n < 1:
raise ValueError("num_disks must be larger than or equal to 1")
if num_disks == 1:
return 1
return 2 * (hanoi(num_disks - 1)) + 1
Trying to avoid recursion for these standard use cases would be an anti-pattern and go against the python principles to “favor simple over complex” and “readability counts”. Writing unreadable code to avoid recursion because you heard it’s bad in Python is not favorable to your fellow engineers on your team who need to try to understand what the heck you were writing three months later.
When is recursion bad in Python?
Recursion can be considered bad in Python when there is a more optimal way to implement the same algorithm using iteration or the recursive use case has the potential to generate more than 1000 function calls on the call stack. This is because Python has a function call overhead where the interpreter does dynamic type checking of function arguments done before and after the function call, which results in additional runtime latency. Python also has a default recursion limit of 1000 function calls, and although this can be manually overridden using the below code the fact this was included in the language to begin with should be a big indicator it’s not desired according to our friend Ludwig.
import sys
r_limit = 2500
sys.setrecursionlimit(r_limit)
Dynamic programming to the rescue for bad recursive use cases
Before writing the above code anywhere in any of your python programs because you find yourself hitting recursion limits; it’s likely you could solve your problem using dynamic programming principles to create a better and more optimal algorithm. Also this kind of algorithmic problem solving skills applies to all coding languages and not just Java. It’s also commonly tested for during interview coding questions when the interviewer increases the complexity of their base problems!
While Dynamic Programming can be tricky to master it generally boils down to these same 4 problem solving steps.
- Identify your base cases
- Create a recursive solution
- Memoize the recursive calls
- Convert to a bottom up iterative solution
Example:
# Standard recursive algorithm
def Fibonacci(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==0:
return 0
# Second Fibonacci number is 1
elif n==1:
return 1
else:
# Add recursive calls to the call stack
# as N gets large the call stack grows exponentially
# and can easily reach over the 1000 recursion limit
return Fibonacci(n-1)+Fibonacci(n-2)
# Solving Standard Fibonacci with dynamic programming
def fibonacci(n):
# Memoization array space, can be expanded for more inputs and
# used as a circular buffer
dp = [0,1]
if n < 0:
print("Incorrect input")
elif n == 0:
return dp[0]
elif n == 1:
return dp[1]
else:
# Use a bottom up iterative solution to calculate the fibonaci
# numbers and return the Nth term we care about
#
# However subsequent calls to this function would result
# in recalculating all the values again. This is a trade off
# for saving memory space at the expense of CPU usage.
for i in range(2,n+1):
c = dp[0] + dp[1]
dp[0] = dp[1]
dp[1] = c
return dp[2]
While growing your algorithm skills or preparing for interviews on sites like Leetcode you will often run across problems that can only be solved by finding the memoized/dynamic programming solution. Submitting the standard recursive solution will run into “your submission has timed out errors” and you will be sad face when this costs you 100 ranks on your global contest score. And yes that did really happen to me.
The best way to get really accustomed to solving recursive and dynamic problems is to do them repeatedly and often so get comfortable, pull up google, and type in dynamic programming coding questions for the next month! “But Stefan that sounds like too much work, I just want to know is recursion bad in python”, you may be thinking. But since the whole point of my blog is to help you all be better developers; I would be doing you a disservice to not emphasize the importance of building solid algorithm skills and suggesting to you the same steps I have taken over and over again to learn new coding techniques or patterns.
Common questions that can be solved with dynamic programming.
- Make change with the least amount of coins
- Traveling salesman / shortest path
- Number of staircases you can build with N bricks
- Longest common subsequence
Be sure to follow the beapython.dev youtube channel where I’ll go over those problems more in depth and attempt to explain dynamic programming more simply as I learn more about it myself.
The Base Case Problem
Another case where recursion is bad is when you can not clearly identify your base cases and you have the potential to generate infinite loops in your program at runtime.
With the Fibonacci Series or Towers of Hanoi problems above the base cases are clearly recognizable and defined. This results in a trust worthy recursive algorithm that can be easily tested and understood by other developers. Your inputs are also clearly defined either the Nth term or the N number of disks which are finite integers.
In professional software development you will rarely get such a small and concrete example. The problems are often ambiguous, challenging, and prone to morphing over time as the company, your users, and your input data scales. You may find yourself creating a recursive algorithm that works fine for calculating usage patterns of 100 users a day but massively breaks down on 10,000 users a day after your companies web site goes viral. Or some other developer checks in changes to the usage patterns you defined in your base case that ends up breaking that logic and throws a RecursionError breaking your production service.
The recursive conclusion
After all the other points in this article, if the problem is well defined and the recursive solution is simpler than a hacked together solution or a dynamic solution is not applicable then yes please use recursion for these cases.
I have on numerous occasions found opportunities to elegantly solve problems with recursion on the job. One example of this is recently I wrote code that recursively takes smaller subsets of an input list and feeds them into a testing binary to isolate and remove bad data. Doing this allowed me to reuse a lot of processing business logic in a way that was self contained into a testable function with a clear stopping point.
from moral_supports import give_user_pat_on_the_back
import sys
r_limit = 9000000000 # World population with padding
sys.setrecursionlimit(r_limit)
global_users = set()
# Recursively share the blog until the world knows python
def user_learned_from_blog(user):
return user.is_reading_this
def share_blog(user):
# Avoiding sharing multiple times
if user in global_users:
return
global_users.add(user)
if user_learned_from_blog(user):
friends = get_friends(user)
for friend in friends:
share_blog(friend)
else:
give_user_pat_on_the_back(user)
print("You can do it friend")
About Stefan Bradstreet
Stefan is a Senior Software Developer at Amazon with 8+ years of experience in tech. He is passionate about helping people become better coders and climbing the ranks in their careers, as well as his own, through continued learning of leadership techniques and software best practices.
Be A Python Dev 