Recursion

A recursive function calls itself on a smaller version of the problem, until it hits a base case simple enough to answer directly. Every recursive function needs both pieces:

def factorial(n):
    if n == 0:          # base case — stops the recursion
        return 1
    return n * factorial(n - 1)   # recursive case — smaller subproblem

Each call to factorial waits on a "call stack" for the call below it to return — that's the same stack data structure from the previous course. Forget the base case, and you recurse forever until Python raises a RecursionError.

Naive recursive Fibonacci is O(2ⁿ) because it re-solves the same subproblems repeatedly. Memoization — caching results you've already computed — turns it into O(n):

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

This is your first taste of dynamic programming: recursion plus a cache of subproblem results, so no subproblem is ever solved twice.