Previous | Tutorial index | Next
Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar sub‑problems. It is a powerful tool for problems that have a naturally recursive structure, such as traversing tree‑like data, processing nested structures, or implementing mathematical sequences like the Fibonacci numbers. However, recursion requires careful design to ensure it terminates—this is achieved with a base case. In this tutorial, we will explore the mechanics of recursion, the importance of the call stack, classic examples, performance considerations, and how to choose between recursion and iteration.
A recursive function is a function that, during its execution, calls itself. This creates a chain of calls that gradually solves smaller instances of the same problem.
Every correct recursive function must have:
Without a base case, the recursion would continue forever (or until Python raises a RecursionError due to depth limit).
When a function calls itself, each call is placed on the call stack. The stack keeps track of each function call's state (local variables, return address). The calls are pushed onto the stack as they are made, and as the base case is reached, the stack unwinds (pops) as each function returns.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
When you call factorial(4):
factorial(4) → n=4, calls factorial(3)
factorial(3) → n=3, calls factorial(2)
factorial(2) → n=2, calls factorial(1)
factorial(1) → base case, returns 1
returns 2*1 = 2
returns 3*2 = 6
returns 4*6 = 24
Each call waits for the result of the next call, then multiplies and returns.
Python limits the recursion depth to prevent stack overflow. The default limit is around 1000. You can check it with sys.getrecursionlimit() and adjust it with sys.setrecursionlimit(limit), but doing so is rarely recommended; it's safer to rewrite the algorithm iteratively or use a different approach.
Mathematically, n! = n * (n-1)! with 0! = 1 (or 1! = 1). Implementation:
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
The Fibonacci sequence: fib(0) = 0, fib(1) = 1, fib(n) = fib(n-1) + fib(n-2).
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
This naive recursive version is highly inefficient due to repeated computations (exponential time). We'll discuss optimizations later.
def sum_list(lst):
if not lst: # empty list base case
return 0
return lst[0] + sum_list(lst[1:])
def reverse_string(s):
if len(s) <= 1:
return s
return reverse_string(s[1:]) + s[0]
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Often more concise and natural for recursive problems (e.g., tree traversal). | Might be more straightforward for simple loops. |
| Performance | Can be slower due to function call overhead; risk of stack overflow. | Usually faster and memory‑efficient (no call stack growth). |
| Space Complexity | O(depth) additional stack space. | O(1) extra space (unless using data structures). |
| Ease of Implementation | Elegant for divide‑and‑conquer, backtracking. | Often easier for sequential operations. |
When to use recursion?
When to avoid recursion?
A recursive function is tail recursive if the recursive call is the very last operation in the function (i.e., the function returns the result of the recursive call directly, without any additional computation). Some languages optimize tail recursion to avoid stack growth, but Python does not perform tail‑call optimization. However, it's still a good conceptual pattern.
Example of tail‑recursive factorial:
def factorial_tail(n, accumulator=1):
if n <= 1:
return accumulator
return factorial_tail(n - 1, n * accumulator)
In Python, this still uses O(n) stack space.
The naive Fibonacci has exponential time because it recalculates the same values many times. We can use memoization (caching results) to make it linear.
memo = {0: 0, 1: 1}
def fib_memo(n):
if n in memo:
return memo[n]
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
Or use functools.lru_cache:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n - 1) + fib_cached(n - 2)
RecursionError.Split the problem into two or more sub‑problems, solve each recursively, and combine the results. Examples: merge sort, quick sort.
Explore all possible solutions by trying choices and undoing (backtracking) when a choice leads to a dead end. Classic examples: N‑Queens, Sudoku solver, generating permutations.
Recursively list all files in a directory and its subdirectories:
import os
def list_files(path):
for entry in os.listdir(path):
full = os.path.join(path, entry)
if os.path.isdir(full):
list_files(full) # recursive call
else:
print(full)
What is the base case in a recursive function?
What will happen if you forget to include a base case?
None.RecursionError.Given def f(n): if n == 0: return 1; return n * f(n-1), what does f(3) return?
6013What does the call stack do during recursion?
True or False: Python performs tail‑call optimization.
What is the main advantage of using recursion over iteration for tree traversal?
How can you improve the performance of a naive Fibonacci recursive function?
What is the default recursion limit in Python?
Which of the following is a tail‑recursive version of factorial?
def fact(n): return 1 if n <=1 else n*fact(n-1)def fact(n, acc=1): return acc if n<=1 else fact(n-1, n*acc)def fact(n): return n * (n-1)def fact(n): return factorial(n)When should you avoid recursion?
Exercise 1: Sum of Digits
Write a recursive function digit_sum(n) that returns the sum of the digits of a non‑negative integer n.
print(digit_sum(123)) # 6
</details>
**Exercise 2: Power with Recursion**
Write a recursive function `power(base, exponent)` that returns `base` raised to the `exponent`.
<details><summary>Sample Solution</summary>
```python
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
print(power(2, 3)) # 8
Exercise 3: Greatest Common Divisor
Write a recursive function gcd(a, b) using Euclid’s algorithm.
print(gcd(48, 18)) # 6
</details>
**Exercise 4: Countdown**
Write a recursive function `countdown(n)` that prints numbers from `n` down to `1`, then `"Blast off!"`.
<details><summary>Sample Solution</summary>
```python
def countdown(n):
if n == 0:
print("Blast off!")
else:
print(n)
countdown(n-1)
countdown(5)
Exercise 5: Palindrome Checker (Recursive)
Write a recursive function is_palindrome(s) that returns True if the string is a palindrome (ignoring spaces and case).
print(is_palindrome("A man a plan a canal Panama")) # True
</details>
---
### 🏠 Homework – Deeper Thinking
#### Short Answer Questions
**1. Recursive Binary Search**
Implement a recursive binary search function `binary_search(arr, target, low, high)` that returns the index or `-1`.
<details><summary>Sample Answer</summary>
```python
def binary_search(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid+1, high)
else:
return binary_search(arr, target, low, mid-1)
2. Tower of Hanoi
Write a recursive function hanoi(n, source, target, auxiliary) that prints the moves.
3. Recursive Permutations
Write a function permutations(sequence) that returns a list of all permutations.
4. Merge Sort (Recursive)
Implement merge sort recursively with merge_sort(arr) and merge(left, right).
def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) return merge(left, right)
</details>
#### Essay Questions
**5. Flatten Nested Lists**
Write a recursive function `flatten(nested_list)` that returns a flat list.
<details><summary>Sample Answer</summary>
```python
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1,2,3,4,5,6]
if low > high: return -1; compute mid; compare.if n == 1: print(f"Move disk 1 from {source} to {target}"); else call hanoi(n-1, source, auxiliary, target), then move the largest disk, then hanoi(n-1, auxiliary, target, source).[[]].In this tutorial, you have learned:
Recursion is a powerful tool that can lead to elegant solutions for certain problems. However, it must be used judiciously, keeping performance and stack depth in mind. With practice, you will develop an intuition for when recursion is the right choice.
Next Steps: In Tutorial 6, we will dive into Higher‑Order Functions and Lambdas, exploring functions that operate on other functions, and the map, filter, and reduce functions.
Happy recursing!