A recursive function calls itself to solve a smaller version of the same problem. Every recursive function needs two things: a **base case** that stops the recursion, and a **recursive case** that moves toward the base case.
```python
def factorial(n):
if n == 0: # base case: stop here
return 1
return n * factorial(n - 1) # recursive case: smaller problem
factorial(4) # 24
```
**What happens on each call — the call stack**
When Python calls a function, it pushes a frame onto the call stack. Each frame holds local variables and a return address. With `factorial(4)`, the stack grows like this:
```
factorial(4) -> calls factorial(3) waits...
factorial(3) -> calls factorial(2) waits...
factorial(2) -> calls factorial(1) waits...
factorial(1) -> calls factorial(0) waits...
factorial(0) -> returns 1 (base case hit!)
factorial(1) returns 1 * 1 = 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24
```
The stack *unwinds* after the base case is reached — each waiting call gets its answer and computes its own return value.
**The most common mistake: forgetting the base case**
Without a base case, recursion never stops — Python raises `RecursionError`:
```python
def bad_factorial(n):
return n * bad_factorial(n - 1) # no base case!
bad_factorial(3) # RecursionError: maximum recursion depth exceeded
```
**Another common mistake: not moving toward the base case**
```python
def also_bad(n):
if n == 0:
return 0
return also_bad(n + 1) # goes away from 0, not toward it!
```
Always verify: does each recursive call make the problem *strictly smaller*?
**Simple example: sum of a list**
```python
def total(lst):
if not lst: # base case: empty list
return 0
return lst[0] + total(lst[1:]) # first element + sum of rest
total([1, 2, 3, 4]) # 10
```
This is less efficient than `sum(lst)` but shows the recursive pattern clearly: split off one element, recurse on the rest, combine.
When recursion is the right tool: trees, divide and conquer
Recursion shines when the problem has a naturally recursive structure: trees, nested data, divide-and-conquer algorithms.
**Binary search** (divide and conquer)
```python
def binary_search(lst, target, lo=0, hi=None):
if hi is None:
hi = len(lst) - 1
if lo > hi: # base case: not found
return -1
mid = (lo + hi) // 2
if lst[mid] == target:
return mid
if lst[mid] < target:
return binary_search(lst, target, mid + 1, hi) # search right half
return binary_search(lst, target, lo, mid - 1) # search left half
binary_search([1, 3, 5, 7, 9], 7) # 3
```
**Tree traversal** (naturally recursive structure)
```python
def tree_sum(node):
if node is None: # base case: empty node
return 0
return node['value'] + tree_sum(node.get('left')) + tree_sum(node.get('right'))
tree = {'value': 1, 'left': {'value': 2, 'left': None, 'right': None},
'right': {'value': 3, 'left': None, 'right': None}}
tree_sum(tree) # 6
```
**Flatten nested lists**
```python
def flatten(lst):
result = []
for item in lst:
if isinstance(item, list):
result.extend(flatten(item)) # recurse into nested list
else:
result.append(item)
return result
flatten([1, [2, [3, 4]], 5]) # [1, 2, 3, 4, 5]
```
**Tail recursion — Python doesn't optimize it**
In some languages (Scheme, Erlang), a recursive call that is the *last* operation in the function (tail call) is optimized by the compiler to reuse the stack frame. Python deliberately does NOT do this (Guido van Rossum: it would make tracebacks unreadable). This means a tail-recursive Python function still creates O(n) stack frames:
```python
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # tail call - but NOT optimized in Python
```
If you need to recurse very deeply (thousands of calls), convert to iteration instead.
Recursion vs iteration, lru_cache, and converting to a stack
**Recursion vs iteration — when to switch**
Recursion is elegant for naturally hierarchical problems. Iteration is often better when: the recursion depth could be large, or the structure is linear (linked list, flat sequence).
```python
# Recursive - clear but O(n) stack frames
def sum_recursive(n):
if n == 0: return 0
return n + sum_recursive(n - 1)
# Iterative - same result, O(1) stack space
def sum_iterative(n):
total = 0
while n > 0:
total += n
n -= 1
return total
```
Python's default recursion limit is 1000. You can raise it with `sys.setrecursionlimit(n)`, but this is a band-aid — large recursion depth is usually a sign you should switch to iteration.
**`functools.lru_cache` — memoize expensive recursive calls**
Without caching, naive Fibonacci recalculates the same subproblems exponentially:
```python
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2) # O(2^n) calls
fib(35) # takes ~2 seconds
```
Add `@lru_cache` and each subproblem is solved once:
```python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n - 1) + fib(n - 2) # O(n) calls now
fib(35) # instant
fib.cache_info() # CacheInfo(hits=..., misses=36, ...)
```
**Converting recursion to iteration with an explicit stack**
Any recursion can be converted to iteration by maintaining your own stack (a list). This avoids Python's recursion limit entirely:
```python
def flatten_iterative(lst):
result = []
stack = [lst]
while stack:
current = stack.pop()
for item in reversed(current):
if isinstance(item, list):
stack.append(item) # push nested list for later
else:
result.append(item)
return result
flatten_iterative([1, [2, [3, 4]], 5]) # [1, 2, 3, 4, 5]
```
**Rule of thumb**: use recursion when the depth is bounded and small (e.g., tree height < 100), and `lru_cache` when subproblems overlap. Switch to iteration (with an explicit stack) when depth is unbounded or performance is critical.
Write a recursive function that returns the nth Fibonacci number. The sequence starts: 0, 1, 1, 2, 3, 5, 8, 13... (fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2)).
def fib(n):
pass
for i in range(8):
print(fib(i), end=" ")
Solution
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(fib(i), end=" ")
def flatten(data):
result = []
for item in data:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
print(flatten([1, [2, [3, [4]], 5], 6]))
Write a recursive function that prints the steps to solve the Tower of Hanoi puzzle for n disks. Move all disks from peg A to peg C using peg B as auxiliary. Print each move as 'Move disk from X to Y'.
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk from {source} to {target}")
return
hanoi(n - 1, source, auxiliary, target)
print(f"Move disk from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
hanoi(3, 'A', 'C', 'B')
No split tab
Cookie preferences
We use necessary cookies to run the site. With your permission, we can also save your site preferences and use analytics and advertising cookies to understand usage and support the project.
Open tools in tabs.Exercises, IDE tools, and trainers stay available as site tabs.
Switch without losing context.Move between explanations, code, and utilities while keeping your place.
Use the sidebar as your map.The left panels hold navigation, settings, files, libraries, and tool controls.
PythonJavaScriptSQLite
One IDE, three practical modes
Python in the browser.Run small scripts, try libraries, and practice API requests without installing anything.
JavaScript for quick experiments.Test browser-friendly code and compare ideas next to your learning materials.
SQLite for data practice.Open the database explorer to inspect tables, write queries, and learn SQL workflows locally.
TopicIDE
Work side by side with split tabs
Keep instructions visible.Open an exercise or reference page beside the IDE instead of jumping back and forth.
Compare tools while you learn.Place regex checks, explanations, and code experiments next to each other when the task needs it.
Close the split when you are done.The workspace returns to a single focused tab, and your open site tabs remain available.
Code Typing Trainer
Or plain text
This trainer is designed for a physical keyboard.Open this section on a laptop or desktop with a wide screen. Touch typing practice will not work correctly on a phone.
Speed: 0 chars/min
0 words/min
Best speed (60s): 0 chars/min
0 words/min
Errors: 0
Total time: 0.0 s
To practice touch typing, avoid looking at your physical keyboard.