Python Recursion - Complete Guide with Examples

What You'll Learn Here

What is recursion — functions that call themselves
Base case vs recursive case — the essential components
Classic examples — factorial, Fibonacci, and more
Tree traversal — real-world applications
Recursion vs iteration — when to use each
Optimization techniques — memoization and tail recursion

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. It's a powerful approach for problems that can be broken down into smaller, similar subproblems.

💡 Key concept: Recursion is like Russian nesting dolls — each doll contains a smaller version of itself. A recursive function solves a problem by solving a smaller instance of the same problem.

Anatomy of a Recursive Function

The Two Essential Parts of Recursion

# Every recursive function has two essential parts:

# 1. Base Case — The stopping condition
# 2. Recursive Case — The function calls itself

# Example: Factorial of n (n!)
# 5! = 5 * 4 * 3 * 2 * 1 = 120

def factorial(n):
    """Calculate factorial of n using recursion"""
    # Base Case: Stop when n is 0 or 1
    if n <= 1:
        return 1
    
    # Recursive Case: n! = n * (n-1)!
    return n * factorial(n - 1)

# How it works:
# factorial(5)
# = 5 * factorial(4)
# = 5 * 4 * factorial(3)
# = 5 * 4 * 3 * factorial(2)
# = 5 * 4 * 3 * 2 * factorial(1)
# = 5 * 4 * 3 * 2 * 1
# = 120

print(factorial(5))  # 120

# Visualizing the call stack:
# Each recursive call adds a new frame to the call stack
# Once the base case is reached, the stack unwinds

# Example with a simple countdown
def countdown(n):
    """Count down from n to 0"""
    # Base Case
    if n < 0:
        return
    
    # Print current number
    print(n)
    
    # Recursive Case
    countdown(n - 1)

countdown(5)
# 5
# 4
# 3
# 2
# 1
# 0

The two essential parts:

Base Case — the condition that stops the recursion
Recursive Case — the function calls itself with a smaller input
Progress — each recursive call moves closer to the base case
Call Stack — each call adds a frame until the base case is reached

Quick Check: What are the two essential parts of a recursive function? (Answer: Base case and recursive case)

Classic Recursive Examples

Recursion in Action

# 1. Fibonacci Sequence
# Each number is the sum of the two preceding ones
# 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

def fibonacci(n):
    """Calculate the nth Fibonacci number"""
    # Base Cases
    if n <= 0:
        return 0
    if n == 1:
        return 1
    
    # Recursive Case
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(7))   # 13
print(fibonacci(10))  # 55

# 2. Sum of a list
def sum_list(numbers):
    """Calculate the sum of a list recursively"""
    # Base Case: Empty list
    if not numbers:
        return 0
    
    # Recursive Case: First element + sum of the rest
    return numbers[0] + sum_list(numbers[1:])

print(sum_list([1, 2, 3, 4, 5]))  # 15

# 3. Reverse a string
def reverse_string(text):
    """Reverse a string using recursion"""
    # Base Case: Empty string or single character
    if len(text) <= 1:
        return text
    
    # Recursive Case: Last character + reverse of the rest
    return text[-1] + reverse_string(text[:-1])

print(reverse_string("hello"))  # "olleh"
print(reverse_string("Python")) # "nohtyP"

# 4. Check if a string is a palindrome
def is_palindrome(text):
    """Check if a string is a palindrome using recursion"""
    # Clean the string: remove spaces and convert to lowercase
    text = text.replace(" ", "").lower()
    
    # Base Case: Empty or single character
    if len(text) <= 1:
        return True
    
    # Base Case: First and last characters don't match
    if text[0] != text[-1]:
        return False
    
    # Recursive Case: Check the middle
    return is_palindrome(text[1:-1])

print(is_palindrome("racecar"))        # True
print(is_palindrome("never odd or even"))  # True
print(is_palindrome("hello"))          # False

# 5. Power calculation (x^n)
def power(base, exponent):
    """Calculate base^exponent using recursion"""
    # Base Cases
    if exponent == 0:
        return 1
    if exponent == 1:
        return base
    
    # Recursive Case
    return base * power(base, exponent - 1)

print(power(2, 3))   # 8
print(power(5, 4))   # 625

Classic recursive problems:

Factorial — n! = n * (n-1)!
Fibonacci — F(n) = F(n-1) + F(n-2)
Sum of list — first + sum(rest)
Reverse string — last + reverse(rest)
Palindrome check — first == last and middle is palindrome
Power calculation — base^exponent = base * base^(exponent-1)

Quick Check: What is the Fibonacci sequence? (Answer: Each number is the sum of the two preceding ones)

Tree Traversal with Recursion

Real-World Applications of Recursion

# Tree traversal is a classic use case for recursion
# Directory structure traversal, file system exploration

# 1. Simulating a tree structure
class TreeNode:
    """A simple tree node"""
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

    def add_child(self, child):
        self.children.append(child)

# 2. Traversing a tree (Depth-First Search)
def dfs(node, depth=0):
    """Depth-first traversal of a tree"""
    print("  " * depth + str(node.value))
    for child in node.children:
        dfs(child, depth + 1)

# 3. Finding a value in a tree
def find_value(node, target):
    """Find a value in a tree recursively"""
    if node.value == target:
        return True
    
    for child in node.children:
        if find_value(child, target):
            return True
    
    return False

# 4. Getting all values from a tree
def get_values(node):
    """Get all values from a tree"""
    result = [node.value]
    for child in node.children:
        result.extend(get_values(child))
    return result

# Example usage
root = TreeNode("Root")
child1 = TreeNode("Child 1")
child2 = TreeNode("Child 2")
child3 = TreeNode("Child 3")

root.add_child(child1)
root.add_child(child2)
child2.add_child(child3)

print("Tree structure:")
dfs(root)
# Root
#   Child 1
#   Child 2
#     Child 3

print("\nContains 'Child 3'?", find_value(root, "Child 3"))  # True
print("Contains 'Child 4'?", find_value(root, "Child 4"))    # False
print("\nAll values:", get_values(root))
# ['Root', 'Child 1', 'Child 2', 'Child 3']

# 5. File system traversal (real-world use)
import os

def list_files(directory, indent=0):
    """List all files in a directory recursively"""
    try:
        items = os.listdir(directory)
        for item in items:
            path = os.path.join(directory, item)
            print("  " * indent + item)
            if os.path.isdir(path):
                list_files(path, indent + 1)
    except PermissionError:
        print("  " * indent + "[Permission Denied]")

# Uncomment to explore your file system
# list_files("/path/to/directory")

Tree traversal use cases:

File system — listing directory contents
XML/JSON parsing — navigating nested structures
Web scraping — traversing DOM trees
Decision trees — exploring decision paths
Game AI — evaluating game states

Quick Check: What is a common real-world use of recursion? (Answer: File system directory traversal)

Recursion vs Iteration

Choosing the Right Approach

# Comparing recursive and iterative solutions

# Problem: Calculate factorial of n

# 1. Recursive Solution
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# 2. Iterative Solution (Loop)
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Problem: Fibonacci sequence

# 3. Recursive (Inefficient)
def fibonacci_recursive(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# 4. Iterative (Efficient)
def fibonacci_iterative(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Comparison table:
print("Comparison of Recursive vs Iterative:")
print("=" * 50)
print(f"Factorial Recursive: {factorial_recursive(10)}")
print(f"Factorial Iterative: {factorial_iterative(10)}")
print(f"Fibonacci Recursive: {fibonacci_recursive(10)}")
print(f"Fibonacci Iterative: {fibonacci_iterative(10)}")

# When to use recursion:
# 1. Problems that have a natural recursive structure (trees)
# 2. Problems that are easier to solve recursively (mathematical)
# 3. Divide and conquer algorithms
# 4. When code clarity is more important than performance

# When to use iteration:
# 1. When performance is critical
# 2. When recursion depth would be too large
# 3. When memory usage is a concern
# 4. For simple, linear problems

Recursion vs Iteration:

Recursion — elegant, natural for tree structures, but memory-intensive
Iteration — efficient, low memory, but can be less readable
Choose recursion — for tree traversal, mathematical problems, clarity
Choose iteration — for performance, large data, simple problems

Quick Check: When should you use recursion instead of iteration? (Answer: When the problem has a natural recursive structure, like trees)

Recursion Optimization

Making Recursion More Efficient

# 1. Memoization (caching results)
# The naive Fibonacci is O(2^n) — very slow

def fibonacci_memoized(n, memo={}):
    """Fibonacci with memoization"""
    if n in memo:
        return memo[n]
    
    if n <= 0:
        memo[n] = 0
        return 0
    if n == 1:
        memo[n] = 1
        return 1
    
    result = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
    memo[n] = result
    return result

print(f"Fibonacci with memoization: {fibonacci_memoized(40)}")
# Fast! O(n) instead of O(2^n)

# 2. Using functools.lru_cache (decorator)
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_cached(n):
    """Fibonacci with built-in caching"""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)

print(f"Fibonacci with lru_cache: {fibonacci_cached(40)}")

# 3. Tail Recursion (Python doesn't optimize, but good practice)
def factorial_tail(n, accumulator=1):
    """Tail-recursive factorial"""
    if n <= 1:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

print(f"Tail-recursive factorial: {factorial_tail(10)}")

# 4. Converting recursion to iteration when needed
# Recursive version with memoization is often enough

# 5. Setting recursion limit
import sys
print(f"Default recursion limit: {sys.getrecursionlimit()}")

# Increase if needed (use with caution)
# sys.setrecursionlimit(2000)

# 6. Time comparison
import time

def time_function(func, n, *args):
    start = time.time()
    result = func(n, *args)
    end = time.time()
    return result, end - start

# Compare performance
n = 30
result1, time1 = time_function(fibonacci_recursive, n)
result2, time2 = time_function(fibonacci_memoized, n)

print(f"\nPerformance Comparison (n={n}):")
print(f"Naive Recursive: {time1:.6f}s")
print(f"Memoized Recursive: {time2:.6f}s")

Optimization techniques:

Memoization — cache results to avoid recomputation
lru_cache — built-in Python caching decorator
Tail recursion — some languages optimize, Python doesn't
Recursion limit — adjust if needed, but use caution
Hybrid approach — use recursion for structure, iteration for performance

Quick Check: What is memoization? (Answer: Caching results to avoid recomputation)

Common Pitfalls and How to Avoid Them

Recursion Traps to Avoid

# 1. Missing Base Case (Infinite Recursion)
# ❌ This will cause RecursionError
# def infinite_recursion():
#     return infinite_recursion()  # No base case!

# 2. Not Moving Toward Base Case
# ❌ This will cause RecursionError
# def not_moving_to_base(n):
#     if n == 0:
#         return
#     return not_moving_to_base(n + 1)  # Moving away from base

# ✅ Always ensure each call moves closer to the base case

# 3. Exceeding Recursion Limit
def recursion_limit_demo(n):
    if n == 0:
        return
    recursion_limit_demo(n - 1)

try:
    recursion_limit_demo(2000)
except RecursionError:
    print("RecursionError: Maximum recursion depth exceeded")
    print("Python's default limit is 1000")

# 4. Inefficient Recursion (Exponential Time)
def bad_fibonacci(n):
    """Naive Fibonacci - O(2^n) time"""
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return bad_fibonacci(n - 1) + bad_fibonacci(n - 2)

print(f"bad_fibonacci(30): {bad_fibonacci(30)}")
print("This was slow! Use memoization for large n")

# 5. Side Effects in Recursion
# ❌ Avoid modifying global state
counter = 0
def recursive_with_side_effect(n):
    global counter
    counter += 1
    if n <= 1:
        return n
    return recursive_with_side_effect(n - 1) + recursive_with_side_effect(n - 2)

# 6. Deeply Nested Structures
# Python's recursion limit can be a problem for deep structures
def traverse_deep_list(lst, depth=0):
    if not isinstance(lst, list):
        return
    for item in lst:
        if isinstance(item, list):
            traverse_deep_list(item, depth + 1)

# 7. Memory Overuse
# Each recursive call adds to the call stack
# For large inputs, this can cause memory issues

# Best Practices Summary:
# 1. Always define a base case
# 2. Ensure progress toward base case
# 3. Use memoization for overlapping subproblems
# 4. Consider recursion depth limits
# 5. Test with small inputs first
# 6. Use iteration when recursion is not natural

Common pitfalls:

Missing base case — causes infinite recursion
Not moving toward base — never reaches stopping condition
Exceeding recursion limit — Python's default is 1000
Inefficient recursion — O(2^n) vs O(n)
Side effects — modifying global state in recursion
Memory overuse — call stack grows with each call

Quick Check: What is the most common recursion pitfall? (Answer: Missing or incorrect base case)

Try It Yourself

Experiment with recursive functions in the editor below. Try implementing your own recursive solutions.

Loading Pyodide... 0%

Python Code Editor

# Python Recursion Practice

print("=" * 40)
print("RECURSION PRACTICE")
print("=" * 40)

# 1. Factorial
print("\n1. FACTORIAL")
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(f"5! = {factorial(5)}")
print(f"7! = {factorial(7)}")

# 2. Fibonacci
print("\n2. FIBONACCI")
def fibonacci(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(f"Fibonacci(7) = {fibonacci(7)}")
print(f"Fibonacci(10) = {fibonacci(10)}")

# 3. Sum of List
print("\n3. SUM OF LIST")
def sum_list(numbers):
    if not numbers:
        return 0
    return numbers[0] + sum_list(numbers[1:])

print(f"Sum of [1,2,3,4,5] = {sum_list([1,2,3,4,5])}")

# 4. Reverse String
print("\n4. REVERSE STRING")
def reverse_string(text):
    if len(text) <= 1:
        return text
    return text[-1] + reverse_string(text[:-1])

print(f"Reverse of 'Python' = '{reverse_string('Python')}'")
print(f"Reverse of 'recursion' = '{reverse_string('recursion')}'")

# 5. Power Function
print("\n5. POWER FUNCTION")
def power(base, exponent):
    if exponent == 0:
        return 1
    if exponent == 1:
        return base
    return base * power(base, exponent - 1)

print(f"2^8 = {power(2, 8)}")
print(f"3^5 = {power(3, 5)}")

# 6. Fibonacci with Memoization
print("\n6. FIBONACCI WITH MEMOIZATION")
from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_cached(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)

print(f"fibonacci_cached(30) = {fibonacci_cached(30)}")

print("\nRecursion practice complete!")

========================================
RECURSION PRACTICE
========================================

1. FACTORIAL
5! = 120
7! = 5040

2. FIBONACCI
Fibonacci(7) = 13
Fibonacci(10) = 55

3. SUM OF LIST
Sum of [1,2,3,4,5] = 15

4. REVERSE STRING
Reverse of 'Python' = 'nohtyP'
Reverse of 'recursion' = 'noisrucer'

5. POWER FUNCTION
2^8 = 256
3^5 = 243

6. FIBONACCI WITH MEMOIZATION
fibonacci_cached(30) = 832040

Recursion practice complete!

🏆

You've Got It!

You now understand recursion in Python — how to write recursive functions, when to use them, and how to optimize them. You've mastered a powerful programming technique!

Quick Quiz

Test what you've learned:

1. What is a recursive function?

A) A function that uses loops B) A function that calls itself C) A function with many parameters D) A function that returns multiple values

2. What is the base case in recursion?

A) The first call to the function B) The condition that stops the recursion C) The recursive call itself D) The return value

3. What is the default recursion limit in Python?

A) 100 B) 1000 C) 10000 D) Unlimited

4. What is memoization?

A) A type of loop B) A way to write recursive functions C) Caching results to avoid recomputation D) A debugging technique

5. Which problem is naturally recursive?

A) Sorting an array B) Traversing a tree C) Finding the average D) Printing a list

Frequently Asked Questions

What is the difference between recursion and iteration?

Recursion uses function calls to repeat operations, with a base case to stop. Iteration uses loops (for, while) to repeat operations. Recursion is more natural for tree-like problems, while iteration is more efficient for simple repetitions.

Why does recursion cause RecursionError?

RecursionError occurs when the recursion depth exceeds Python's limit (default 1000). This happens when the base case is missing, incorrect, or when the input is too large. You can increase the limit with sys.setrecursionlimit(), but it's better to use iteration for very deep recursion.

What is memoization and why is it useful?

Memoization is a technique where you cache the results of expensive function calls and return the cached result when the same inputs occur again. It's especially useful in recursion to avoid redundant computation, as seen in the Fibonacci sequence.

What's a common interview question about recursion?

Common questions include: "Explain recursion with an example," "What is the difference between recursion and iteration?" "What is memoization and how does it work?" and "Write a recursive function to solve problem X."

Can every recursive function be converted to iteration?

Yes, every recursive function can be converted to an iterative one using loops and an explicit stack. However, the recursive version is often more readable and natural for certain problems like tree traversal.

What is tail recursion?

Tail recursion is when the recursive call is the last operation in the function. Some languages optimize tail recursion to avoid stack growth. Python does not perform tail recursion optimization, so it's not as important in Python.

Where to Go From Here

Now that you understand recursion, check out these related topics:

Previous: Nesting of Functions Next: Global, Local and Non-Local →

Python

Python: Recursion

What is Recursion?

Anatomy of a Recursive Function

The Two Essential Parts of Recursion

Classic Recursive Examples

Recursion in Action

Tree Traversal with Recursion

Real-World Applications of Recursion

Recursion vs Iteration

Choosing the Right Approach

Recursion Optimization

Making Recursion More Efficient

Common Pitfalls and How to Avoid Them

Recursion Traps to Avoid

Try It Yourself

You've Got It!

Quick Quiz

Frequently Asked Questions

What is the difference between recursion and iteration?

Why does recursion cause RecursionError?

What is memoization and why is it useful?

What's a common interview question about recursion?

Can every recursive function be converted to iteration?

What is tail recursion?

Where to Go From Here

Global, Local, and Non-Local

Lambda Functions

📝 Assignments

Python

Python: Recursion

What is Recursion?

Anatomy of a Recursive Function

The Two Essential Parts of Recursion

Classic Recursive Examples

Recursion in Action

Tree Traversal with Recursion

Real-World Applications of Recursion

Recursion vs Iteration

Choosing the Right Approach

Recursion Optimization

Making Recursion More Efficient

Common Pitfalls and How to Avoid Them

Recursion Traps to Avoid

Try It Yourself

You've Got It!

Quick Quiz

Frequently Asked Questions

What is the difference between recursion and iteration? ▼

Why does recursion cause RecursionError? ▼

What is memoization and why is it useful? ▼

What's a common interview question about recursion? ▼

Can every recursive function be converted to iteration? ▼

What is tail recursion? ▼

Where to Go From Here

Global, Local, and Non-Local

Lambda Functions

📝 Assignments

What is the difference between recursion and iteration?

Why does recursion cause RecursionError?

What is memoization and why is it useful?

What's a common interview question about recursion?

Can every recursive function be converted to iteration?

What is tail recursion?