Recursion
1. The Core Mechanics
Every recursive function requires two things:
- Base Case: The condition that stops the recursion.
- General (Recursive) Case: The part where the function calls itself with a simpler version of the original problem.
# 1. Factorial (n!)
def factorial(n):
if n == 0: # Base Case
return 1
else: # Recursive Case
return n * factorial(n - 1)
# 2. Fibonacci Sequence
def fib(n):
if n <= 1: # Base Case
return n
else:
return fib(n-1) + fib(n-2)
# 3. Compound Interest
def compound(p, r, t):
if t == 0: # End of term
return p
else:
return compound(p * (1 + r), r, t - 1)
# 4. Binary Search (Recursive)
def bin_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x: return mid
elif arr[mid] > x:
return bin_search(arr, low, mid-1, x)
else:
return bin_search(arr, mid+1, high, x)
return -1
2. The Stack: Winding & Unwinding
When a function calls itself, the current state (local variables and return address) is pushed onto the Call Stack. This is Winding. Once the base case is reached, the stack Unwinds, returning values back up the chain.
Visualizing factorial(3)
factorial(1) → Returns 1 (BASE CASE)
↑ ↓
factorial(2) → Waits for 2 * 1
↑ ↓
factorial(3) → Waits for 3 * (result of 2)
The green arrows represent Unwinding (Returning values), the red represent Winding.
⚠️ Exam Note: Iterative vs. Recursive
A2 exams often ask to compare the two. Recursion is usually shorter and more elegant, but Iteration (loops) is more memory-efficient because it doesn't build up a massive call stack.