Recursion Basics — The Complete Beginner

Master recursion from the ground up — what recursion is, how the call stack works, the three laws of recursion, base cases and recursive cases, common recursion patterns, visualizing recursion trees, and avoiding infinite recursion and stack overflow.

Introduction

Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller, simpler instances of the same problem.

The concept sounds circular — a function calling itself — and it is, intentionally so. The key is that each recursive call works on a *smaller* version of the problem. Eventually, the problem becomes so small it can be solved directly without further recursion. This stopping point is the base case.

Recursion is not just a coding trick. It is a fundamental way of thinking about problems that decomposes naturally into similar subproblems. It is the foundation of divide-and-conquer algorithms, tree traversal, dynamic programming, and backtracking.

How Recursion Works — The Call Stack

Every function call in Python (and most languages) creates a stack frame on the call stack. A stack frame stores:

The function's local variables
The function's parameters
Where to return to when the function finishes

Recursive calls stack these frames. When the base case is reached, frames start unwinding (returning values up the chain).

Factorial Example — Full Trace

python example

def factorial(n):
    if n <= 1:         # Base case
        return 1
    return n * factorial(n - 1)   # Recursive case

factorial(5)

Call stack progression:

factorial(5) called	Stack: [factorial(5)]
└── calls factorial(4)	Stack: [factorial(5), factorial(4)]
└── calls factorial(3)	Stack: [..., factorial(3)]
└── calls factorial(2)	Stack: [..., factorial(2)]
└── calls factorial(1)	Stack: [..., factorial(1)]
└── BASE CASE	returns 1 ← unwind begins

This is why recursion uses memory proportional to the depth of recursion — each active call occupies space on the stack.

The Three Laws of Recursion

Every correct recursive algorithm must obey these three laws:

Law 1: A recursive algorithm must have a base case. Without a base case, the function calls itself forever → stack overflow.

Law 2: A recursive algorithm must change its state and move toward the base case. Each recursive call must work on a smaller/simpler version of the problem. If the input never changes, you never reach the base case.

Law 3: A recursive algorithm must call itself, recursively. This is the definition — the function must call itself for the recursive part of the solution.

Classic Recursion Examples

Example 1 — Factorial

python example

def factorial(n):
    """n! = n × (n-1) × (n-2) × ... × 1"""
    if n <= 1:           # Base case: 0! = 1! = 1
        return 1
    return n * factorial(n - 1)   # Recursive: n! = n × (n-1)!

print(factorial(5))   # 120
print(factorial(0))   # 1

Recurrence: T(n) = T(n-1) + O(1) → O(n) time, O(n) space

Example 2 — Fibonacci

python example

def fibonacci(n):
    """F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1"""
    if n <= 1:           # Base cases
        return n
    return fibonacci(n-1) + fibonacci(n-2)   # Two recursive calls!

print(fibonacci(6))   # 8 (0,1,1,2,3,5,8)

Warning: Naive Fibonacci is O(2ⁿ) — exponential! For large n, use memoization or iteration.

Example 3 — Sum of Array

Example

def array_sum(arr, index=0): """Sum all elements recursively.""" if index == len(arr): # Base case: past the last element return 0 return arr[index] + array_sum(arr, index + 1) print(array_sum([1, 2, 3, 4, 5])) # 15

Example 4 — Power Function

python example

def power(base, exp):
    """base^exp using recursion."""
    if exp == 0:           # Base case: anything^0 = 1
        return 1
    return base * power(base, exp - 1)

# Optimized — O(log n):
def fast_power(base, exp):
    if exp == 0: return 1
    if exp % 2 == 0:
        half = fast_power(base, exp // 2)
        return half * half   # Only one recursive call for even exponent
    return base * fast_power(base, exp - 1)

print(fast_power(2, 10))   # 1024

Example 5 — String Reversal

Example

def reverse_string(s): if len(s) <= 1: # Base case return s return reverse_string(s[1:]) + s[0] # Last chars + first char print(reverse_string("hello")) # "olleh"

Recursion Tree Visualization

A recursion tree shows all recursive calls as a tree structure — invaluable for understanding complexity.

Example

fibonacci(4): fib(4) / \ fib(3) fib(2) / \ / \ fib(2) fib(1) fib(1) fib(0) / \ fib(1) fib(0) Total calls: 9 for fib(4). For fib(n): ~2ⁿ calls.

Reading the recursion tree:

Each node = one function call
Total nodes = total operations
Height = maximum recursion depth = stack space
Width of bottom level = number of base case calls

Common Recursion Patterns

Pattern 1 — Linear Recursion (Single Call)

python example

def sum_to_n(n):
    if n == 0: return 0
    return n + sum_to_n(n - 1)   # One recursive call
# Depth: n, Time: O(n), Space: O(n)

Pattern 2 — Binary Recursion (Two Calls)

python example

def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)   # Two recursive calls
# Depth: n, Time: O(2ⁿ), Space: O(n) — branching!

Pattern 3 — Divide-and-Conquer (Halving)

Example

def binary_search(arr, target, left, right): if left > right: return -1 mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid+1, right) else: return binary_search(arr, target, left, mid-1) # One call, halving input. Depth: log n, Time: O(log n), Space: O(log n)

Pattern 4 — Tail Recursion

python example

def factorial_tail(n, accumulator=1):
    """Tail recursive: recursive call is the LAST operation."""
    if n <= 1: return accumulator
    return factorial_tail(n-1, n * accumulator)   # Tail call — no work after return
# Can be optimized to O(1) space in languages with tail-call optimization (not Python)

Infinite Recursion and Stack Overflow

python example

# WRONG — no base case
def infinite_sum(n):
    return n + infinite_sum(n - 1)   # Never stops!
# RecursionError: maximum recursion depth exceeded

# WRONG — base case never reached
def wrong_factorial(n):
    if n == 0: return 1
    return n * wrong_factorial(n + 1)   # Going UP, not toward 0!

# WRONG — base case unreachable for negative input
def sum_recursive(n):
    if n == 0: return 0
    return n + sum_recursive(n - 1)   # Works for n>=0, fails for n<0

Python's default recursion limit is ~1000. Check and adjust if needed:

python example

import sys
print(sys.getrecursionlimit())   # 1000
sys.setrecursionlimit(10000)     # Increase (use carefully!)

Recursion vs Iteration

Any recursive solution can be rewritten iteratively (using an explicit stack if needed). Key comparison:

Aspect	Recursion	Iteration
Code clarity	Often cleaner, more natural	Can be verbose
Space	O(depth) stack frames	O(1) typically
Performance	Function call overhead	Faster in practice
Stack overflow risk	Yes (deep recursion)	No
Natural for	Trees, graphs, divide-and-conquer	Simple loops

python example

# Recursive factorial — clean but O(n) stack
def fact_recursive(n):
    return 1 if n <= 1 else n * fact_recursive(n-1)

# Iterative factorial — O(1) stack
def fact_iterative(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

Summary

Recursion = a function that calls itself on smaller inputs until a base case is reached.

Three requirements:

Base case (stopping condition)
Progress toward base case (smaller input each call)
Self-call (the recursive step)

Call stack: Each call adds a frame; unwinds when base case is returned.

Space: O(max recursion depth) — always count this!

Common patterns: Linear (n calls), Binary (2ⁿ calls), Divide-and-conquer (log n levels)

Use when: The problem naturally decomposes into smaller identical subproblems (trees, divide-and-conquer, backtracking).

*Next Lesson: Tail Recursion — Special recursion where the call is the last operation, enabling space optimization.*

Introduction

Recursion is a technique where a function calls itself to solve a problem by breaking it into smaller, simpler instances of the same problem.

How Recursion Works — The Call Stack

Every function call in Python (and most languages) creates a stack frame on the call stack. A stack frame stores:

The function's local variables
The function's parameters
Where to return to when the function finishes

Recursive calls stack these frames. When the base case is reached, frames start unwinding (returning values up the chain).

Factorial Example — Full Trace

python example

def factorial(n):
    if n <= 1:         # Base case
        return 1
    return n * factorial(n - 1)   # Recursive case

factorial(5)

Call stack progression:

factorial(5) called	Stack: [factorial(5)]
└── calls factorial(4)	Stack: [factorial(5), factorial(4)]
└── calls factorial(3)	Stack: [..., factorial(3)]
└── calls factorial(2)	Stack: [..., factorial(2)]
└── calls factorial(1)	Stack: [..., factorial(1)]
└── BASE CASE	returns 1 ← unwind begins

This is why recursion uses memory proportional to the depth of recursion — each active call occupies space on the stack.

The Three Laws of Recursion

Every correct recursive algorithm must obey these three laws:

Law 1: A recursive algorithm must have a base case. Without a base case, the function calls itself forever → stack overflow.

Law 3: A recursive algorithm must call itself, recursively. This is the definition — the function must call itself for the recursive part of the solution.

Classic Recursion Examples

Example 1 — Factorial

python example

def factorial(n):
    """n! = n × (n-1) × (n-2) × ... × 1"""
    if n <= 1:           # Base case: 0! = 1! = 1
        return 1
    return n * factorial(n - 1)   # Recursive: n! = n × (n-1)!

print(factorial(5))   # 120
print(factorial(0))   # 1

Recurrence: T(n) = T(n-1) + O(1) → O(n) time, O(n) space

Example 2 — Fibonacci

python example

def fibonacci(n):
    """F(n) = F(n-1) + F(n-2), F(0)=0, F(1)=1"""
    if n <= 1:           # Base cases
        return n
    return fibonacci(n-1) + fibonacci(n-2)   # Two recursive calls!

print(fibonacci(6))   # 8 (0,1,1,2,3,5,8)

Warning: Naive Fibonacci is O(2ⁿ) — exponential! For large n, use memoization or iteration.

Example 3 — Sum of Array

Example

Example 4 — Power Function

python example

def power(base, exp):
    """base^exp using recursion."""
    if exp == 0:           # Base case: anything^0 = 1
        return 1
    return base * power(base, exp - 1)

# Optimized — O(log n):
def fast_power(base, exp):
    if exp == 0: return 1
    if exp % 2 == 0:
        half = fast_power(base, exp // 2)
        return half * half   # Only one recursive call for even exponent
    return base * fast_power(base, exp - 1)

print(fast_power(2, 10))   # 1024

Example 5 — String Reversal

Example

def reverse_string(s): if len(s) <= 1: # Base case return s return reverse_string(s[1:]) + s[0] # Last chars + first char print(reverse_string("hello")) # "olleh"

Recursion Tree Visualization

A recursion tree shows all recursive calls as a tree structure — invaluable for understanding complexity.

Example

fibonacci(4): fib(4) / \ fib(3) fib(2) / \ / \ fib(2) fib(1) fib(1) fib(0) / \ fib(1) fib(0) Total calls: 9 for fib(4). For fib(n): ~2ⁿ calls.

Reading the recursion tree:

Each node = one function call
Total nodes = total operations
Height = maximum recursion depth = stack space
Width of bottom level = number of base case calls

Common Recursion Patterns

Pattern 1 — Linear Recursion (Single Call)

python example

def sum_to_n(n):
    if n == 0: return 0
    return n + sum_to_n(n - 1)   # One recursive call
# Depth: n, Time: O(n), Space: O(n)

Pattern 2 — Binary Recursion (Two Calls)

python example

def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)   # Two recursive calls
# Depth: n, Time: O(2ⁿ), Space: O(n) — branching!

Pattern 3 — Divide-and-Conquer (Halving)

Example

Pattern 4 — Tail Recursion

python example

def factorial_tail(n, accumulator=1):
    """Tail recursive: recursive call is the LAST operation."""
    if n <= 1: return accumulator
    return factorial_tail(n-1, n * accumulator)   # Tail call — no work after return
# Can be optimized to O(1) space in languages with tail-call optimization (not Python)

Infinite Recursion and Stack Overflow

python example

# WRONG — no base case
def infinite_sum(n):
    return n + infinite_sum(n - 1)   # Never stops!
# RecursionError: maximum recursion depth exceeded

# WRONG — base case never reached
def wrong_factorial(n):
    if n == 0: return 1
    return n * wrong_factorial(n + 1)   # Going UP, not toward 0!

# WRONG — base case unreachable for negative input
def sum_recursive(n):
    if n == 0: return 0
    return n + sum_recursive(n - 1)   # Works for n>=0, fails for n<0

Python's default recursion limit is ~1000. Check and adjust if needed:

python example

import sys
print(sys.getrecursionlimit())   # 1000
sys.setrecursionlimit(10000)     # Increase (use carefully!)

Recursion vs Iteration

Any recursive solution can be rewritten iteratively (using an explicit stack if needed). Key comparison:

Aspect	Recursion	Iteration
Code clarity	Often cleaner, more natural	Can be verbose
Space	O(depth) stack frames	O(1) typically
Performance	Function call overhead	Faster in practice
Stack overflow risk	Yes (deep recursion)	No
Natural for	Trees, graphs, divide-and-conquer	Simple loops

python example

# Recursive factorial — clean but O(n) stack
def fact_recursive(n):
    return 1 if n <= 1 else n * fact_recursive(n-1)

# Iterative factorial — O(1) stack
def fact_iterative(n):
    result = 1
    for i in range(2, n+1):
        result *= i
    return result

Summary

Recursion = a function that calls itself on smaller inputs until a base case is reached.

Three requirements:

Base case (stopping condition)
Progress toward base case (smaller input each call)
Self-call (the recursive step)

Call stack: Each call adds a frame; unwinds when base case is returned.

Space: O(max recursion depth) — always count this!

Common patterns: Linear (n calls), Binary (2ⁿ calls), Divide-and-conquer (log n levels)

Use when: The problem naturally decomposes into smaller identical subproblems (trees, divide-and-conquer, backtracking).

*Next Lesson: Tail Recursion — Special recursion where the call is the last operation, enabling space optimization.*

Introduction

How Recursion Works — The Call Stack

Factorial Example — Full Trace

The Three Laws of Recursion

Classic Recursion Examples

Example 1 — Factorial

Example 2 — Fibonacci

Example 3 — Sum of Array

Example 4 — Power Function

Example 5 — String Reversal

Recursion Tree Visualization

Common Recursion Patterns

Pattern 1 — Linear Recursion (Single Call)

Pattern 2 — Binary Recursion (Two Calls)

Pattern 3 — Divide-and-Conquer (Halving)

Pattern 4 — Tail Recursion

Infinite Recursion and Stack Overflow

Recursion vs Iteration

Summary

Continue learning this concept

Introduction

How Recursion Works — The Call Stack

Factorial Example — Full Trace

The Three Laws of Recursion

Classic Recursion Examples

Example 1 — Factorial

Example 2 — Fibonacci

Example 3 — Sum of Array

Example 4 — Power Function

Example 5 — String Reversal

Recursion Tree Visualization

Common Recursion Patterns

Pattern 1 — Linear Recursion (Single Call)

Pattern 2 — Binary Recursion (Two Calls)

Pattern 3 — Divide-and-Conquer (Halving)

Pattern 4 — Tail Recursion

Infinite Recursion and Stack Overflow

Recursion vs Iteration

Summary

Continue learning this concept