When people hear the word recursion, they often imagine a function calling itself over and over, a concept that can feel both magical and confusing at first. It is one of those ideas in programming that seems almost abstract, like a puzzle that only the code can solve. Beginners often struggle with it, and even experienced developers occasionally trip over its quirks.
Yes, recursion is just a function calling itself. But it is more than syntax or logic: it is a way of thinking. It teaches you how to break problems into smaller, manageable pieces, a skill that is at the heart of algorithmic problem solving. Whether you are traversing a tree, generating combinations, or sorting data efficiently, recursion shows up everywhere in computer science.
“Any fool can write code that a computer can understand. Good programmers write code that humans can understand.” – Martin Fowler
In this article, I will walk you through three common recursion mistakes in Python, the ones that beginners stumble on the most and show you how to fix them.
What and Why Recursion?
The trick lies in thinking about problems in smaller, repeatable steps.
Recursion is essentially a way to divide a problem into sub-problems, solve each of them, and then combine the results. It is like climbing a staircase by taking one step at a time: you do not leap to the top in one bound, you handle each step individually until you reach the goal.
Here is a simple example in Python, calculating the factorial of a number:
def factorial(n):
if n == 0: #base case: stop the recursion
return 1
return n * factorial(n-1) #recursive case: call the function itself
print(factorial(5)) #output: 120In this example, factorial(5) calls factorial(4), which calls factorial(3), and so on, until it reaches the base case of n == 0. Then, the results multiply back up the chain. Each recursive call is simple on its own, but together they solve the larger problem.
Mistake 1: Missing the Base Case
One of the first things every beginner learns about recursion is that you must define a stopping point. Otherwise, the function will keep calling itself forever. Surprisingly, this is also one of the most common mistakes I see, even among students who have been coding for a while.
Think of recursion like climbing a ladder. If you never reach the top, you will just keep stepping upwards without ever stopping. In code, forgetting the base case leads to a RecursionError or, in in other words, an endless loop that your computer cannot escape.
Here is an example of a function missing its base case:
def factorial(n):
return n * factorial(n-1) #missing base caseIf we call factorial(5), Python will keep calling factorial(4), factorial(3), and so on, never stopping. Eventually, it will crash.
The fix is simple: always include a base case, the condition that tells the function when to stop calling itself. Here is the corrected version:
def factorial(n):
if n == 0: #base case
return 1
return n * factorial(n-1)Pro tip: When writing recursion, always ask yourself: “What is the simplest input where I do not need to recurse?” That is usually your base case.
Mistake 2: Modifying Original Data
Another common recursion pitfall is changing the original data inside a recursive function. At first, it might seem convenient to just pop an element from a list or alter a variable in place, but this often leads to unexpected results.
Think of recursion like a series of mirrors reflecting an image. Each call is a reflection of the previous one. If you change the original mirror, every reflection can become distorted. Similarly, modifying the original data inside a recursive call can make your function behave unpredictably.
Here is an example that might look fine at first:
def reverse_list(lst):
if not lst:
return []
lst.pop() #modifying the original list
return lstIf you try reverse_list([1, 2, 3, 4]), the function does not return the reversed list you expect. The original list is being altered as the recursion progresses, causing confusion and potential bugs.
The solution is to work on a copy of the data or return new values instead of changing the original. Here is a fixed version:
def reverse_list(lst):
if not lst:
return []
return [lst[-1]] + reverse_list(lst[:-1])Now, each recursive call works with a fresh slice of the list, leaving the original intact.
Mistake 3: Inefficient Recursive Calls
Even if you have mastered the base case and avoid modifying data, recursion can still slow your code down dramatically if you are recalculating the same subproblems over and over. Many beginners are surprised that their function works correctly but is painfully slow for larger inputs.
Think of it like exploring a maze: if you keep retracing the same paths without remembering where you have been, you will spend way more time than necessary.
A good example is counting the number of paths in a grid. Imagine a 2×2 grid and you want to move from the top-left corner to the bottom-right, moving only right or down.
Here is a naive recursive solution:
def count_paths(m, n):
if m == 1 or n == 1: #base case: only one way to reach the end
return 1
return count_paths(m-1, n) + count_paths(m, n-1)This works fine for small grids, but as the grid grows, the function recalculates the same subproblems multiple times. For example, count_paths(2,3) might be computed repeatedly in different branches of the recursion, which blows up exponentially.
The solution is to store results of subproblems, a technique called memoization. This ensures each subproblem is only solved once:
memo = {}
def count_paths(m, n):
if (m, n) in memo:
return memo[(m, n)]
if m == 1 or n == 1:
memo[(m, n)] = 1
else:
memo[(m, n)] = count_paths(m-1, n) + count_paths(m, n-1)
return memo[(m, n)]Pro tip: Whenever a recursive function feels slower than expected, ask yourself: “Am I recalculating the same problem multiple times?”
Practice Time!
Problem:
Write a recursive Python function that counts how many numbers in a list are greater than 0.
Example:
Input: [3, -1, 0, 7, 4, -5] Output: 3 #3, 7, 4 are positive
- Use an index parameter to avoid slicing the list.
- Think about the base case: when the index reaches the end of the list, return 0.
- Add 1 if the current number is positive, otherwise add 0.
Try solving yourself before looking at the solution!
Solution
def count_positive(lst, i=0):
#base case: reached the end of the list
if i == len(lst):
return 0
#check if current number is positive
current = 1 if lst[i] > 0 else 0
#recursive call for the next index
return current + count_positive(lst, i + 1)
#example usage
numbers = [3, -1, 0, 7, 4, -5]
print(count_positive(numbers)) #output: 3How it works (step by step):
- Base case: When the index i reaches the end of the list, return 0 (no more elements to check).
- Check current element: If it is positive, add 1; otherwise, add 0.
- Recursive call: Move to the next index (i + 1) and repeat.
- Accumulate result: Each call returns the count for its element plus the count from the rest of the list.
Resources
If you enjoyed this post and want to follow my coding journey, tips, and projects, be sure to connect with me! 👾 📥
- Check out my latest projects and code on GitHub.
- Follow me on Instagram and Linkedin for quick tips, behind-the-scenes, and tech life updates.
- Interested in working together or seeing my full experience? Take a look at my Portfolio.
I would love to hear your thoughts on common coding mistakes, feel free to reach out anytime!