Recursion

A recursive function calls itself to solve smaller instances of the same problem, until a base case stops the recursion.

Anatomy of a recursive function

1. Base case — the condition that stops recursion (prevents infinite calls).
2. Recursive case — the function calls itself with a smaller/simpler input.

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)   # recursive case

print(factorial(5))   # 120

Call stack trace for factorial(4)

factorial(4)
  -> 4 * factorial(3)
       -> 3 * factorial(2)
            -> 2 * factorial(1)
                 -> returns 1  (base case)
            <- returns 2 * 1 = 2
       <- returns 3 * 2 = 6
  <- returns 4 * 6 = 24

Example: Fibonacci sequence

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i), end=" ")   # 0 1 1 2 3 5 8 13

Example: Sum of first n natural numbers

def sum_n(n):
    if n == 0:
        return 0
    return n + sum_n(n - 1)

print(sum_n(5))   # 15

Example: Reverse a string using recursion

def reverse_str(s):
    if len(s) == 0:
        return s
    return reverse_str(s[1:]) + s[0]

print(reverse_str("python"))   # nohtyp

Recursion vs Iteration

import sys
print(sys.getrecursionlimit())   # default recursion limit, usually 1000

Every recursive function must have a correctly reachable base case, or it will recurse infinitely and raise RecursionError: maximum recursion depth exceeded.