Recursion in Python
Subject: Data Structures and Algorithms · Language: Python · Level: beginner · 8 min read
Learn recursive functions, base case, recursive case, call stack, factorial tracing, recursion limits, and DSA recursion use cases in Python.
Recursion means a function calls itself to solve a smaller version of the same problem. Instead of solving everything directly, the function reduces the problem step by step until it reaches a simple case.
Every recursive function must have a base case. The base case is the stopping condition. Without it, the function keeps calling itself and eventually causes a recursion error because too many calls are stored in memory.
Every recursive function also needs a recursive case. This is the part where the function calls itself with smaller or simpler input. The input must move toward the base case, otherwise the recursion will not stop correctly.
The call stack is used to store unfinished function calls. When a recursive call is made, the current function waits. After the base case returns, the waiting calls complete one by one in reverse order.
A good way to understand recursion is to trace a small input. For factorial of 3, the calls go down as `factorial(3)`, `factorial(2)`, `factorial(1)`. Then answers return upward: 1, then 2, then 6.
Recursion is important in DSA because trees, graphs, backtracking, divide-and-conquer, and dynamic programming often have repeated smaller structures. Learning recursion slowly and clearly makes advanced topics easier.
A recursive solution is useful when the problem naturally repeats the same pattern. Factorial, tree traversal, graph DFS, backtracking, divide-and-conquer, and dynamic programming commonly use recursion.
For beginners, recursion can feel confusing because a function call does not finish immediately. Python keeps each unfinished function call in memory until the smallest case is reached. Then the answers return step by step.
What Is a Recursive Function?
A recursive function is a function that calls itself.
```python
def show():
show()
```
This example is unsafe because it never stops. A correct recursive function must have a stopping condition.
Base Case
The base case is the stopping condition of recursion. It tells the function when the problem has become small enough to answer directly.
Without a correct base case, the function keeps calling itself again and again. This can crash the program with a recursion depth error.
```python
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
```
Sample Output after calling `countdown(3)`
```text
3
2
1
```
Here, `n == 0` is the base case. When `n` becomes 0, the function returns and stops making more calls.
Recursive Case
The recursive case is the part where the function calls itself with a smaller or simpler input.
The smaller input must move toward the base case. If it does not, recursion will not stop.
In factorial, `factorial(n)` calls `factorial(n - 1)`. The value of `n` decreases, so it eventually reaches 1 or 0.
Call Stack
The call stack is the memory area where Python keeps track of active function calls.
Every recursive call is placed on the stack. When the base case returns an answer, Python starts completing the pending calls in reverse order.
A simple way to remember recursion is: recursion goes down by making smaller calls, then comes back up by returning answers.
Factorial Meaning
Factorial of 5 means `5 * 4 * 3 * 2 * 1`, which is 120.
Mathematically, factorial can be defined recursively:
```text
factorial(n) = n * factorial(n - 1)
factorial(1) = 1
```
This definition directly becomes a recursive function.
Factorial Code
```python
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
```
The condition `n == 0 or n == 1` is the base case. The line `return n * factorial(n - 1)` is the recursive case.
Recursion Trace
For `factorial(5)`, the calls go down like this:
```text
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
```
When `factorial(1)` returns 1, the answers come back up like this:
```text
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120
```
Tracing small examples by hand is one of the best ways to understand recursion.
Recursion vs Loop
Both recursion and loops can repeat work. A loop repeats using `for` or `while`, while recursion repeats by calling the same function again.
Use recursion when the problem is naturally made of smaller similar problems, such as trees, backtracking, and divide-and-conquer. Use loops when simple repetition is clearer, such as printing numbers or summing list values.
Python Recursion Limit
Python has a recursion depth limit to prevent infinite recursion from using too much memory. If recursion goes too deep, Python raises `RecursionError`.
For very deep problems, an iterative solution may be safer. Beginners should first focus on writing a correct base case and a recursive call that moves toward it.
Common Mistakes in Recursion
- Missing the base case
- Writing a base case that is never reached
- Not reducing the input toward the base case
- Forgetting to return the recursive result
- Using recursion where a simple loop would be clearer
Whenever recursion fails, check these points first.
Where Recursion Is Used in DSA
Recursion is used in tree traversal, graph DFS, backtracking, binary search, merge sort, quick sort, and dynamic programming.
Many advanced DSA topics become easier when recursion is clear. That is why students should learn recursion slowly and focus on base case, recursive case, and return value.
Example Program
```python
def factorial(n):
if n == 0 or n == 1:
return 1
return n * factorial(n - 1)
n = int(input("Enter n: "))
print("Factorial =", factorial(n))
```
Sample Input
```text
5
```
Output
```text
Enter n: Factorial = 120
```
This program reads a number and calculates its factorial using recursion.
Every recursive solution has two responsibilities. First, it must know when to stop. This is the base case. Second, it must reduce the problem toward that stopping point. This is the recursive case.
If either responsibility is missing, recursion becomes unsafe. Without a base case, the function keeps calling itself. Without progress toward the base case, the function may still never stop even if a base case exists.
Recursion uses the call stack. Each unfinished function call waits in memory until the smaller call returns. This is why recursion can solve nested problems naturally, but it can also use more memory than a loop.
In DSA, recursion becomes especially powerful in trees and backtracking. A tree naturally splits into smaller subtrees, and backtracking naturally tries one choice, explores it, and then returns to try another choice.
Practice Question
Write a recursive function to calculate the sum of numbers from 1 to n. Then write the same solution using a loop and compare both approaches.