Recursion

Recursion

Recursion is a function that calls itself to solve a smaller version of the same problem. Every recursive function needs a base case that stops it.

Factorial

def fact(n):\n    if n <= 1:        # base case\n        return 1\n    return n * fact(n - 1)

Fibonacci

def fib(n):\n    if n <= 1:\n        return n\n    return fib(n - 1) + fib(n - 2)\n\n# fib(6) == 8

The recursion checklist

• What is the smallest case? (base case)
• Does each call get smaller?
• Will it reach the base case?
• What is the return value at each level?

Watch the stack

def forever():\n    return forever()\n\n# RecursionError: maximum recursion depth exceeded

Recursion vs loops

Anything recursive can be written with a loop. Recursion shines on tree-like and divide-and-conquer problems; loops are usually faster and safer for simple ones.

A tree walk (directory)

import os\n\ndef walk(path, depth=0):\n    for entry in os.listdir(path):\n        full = os.path.join(path, entry)\n        print("  " * depth + entry)\n        if os.path.isdir(full):\n            walk(full, depth + 1)

Tip: Draw the call chain on paper for fib(5). Seeing recursion as a tree of calls is the moment it finally clicks.