Recursive Functions Lab: from n! to Fib(n)

Predict and trace recursive processes (linear vs tree recursion), then implement recursive, iterative, and memoized procedures to compare process shape and cost.

0. Predict the Expansion/Contraction Log (Factorial)

Before running anything, **predict** the returned value and the exact `log` list.

Code to reason about:
```python
def fact_log(n, log):
    log.append(f"enter {n}")
    if n == 0:
        log.append("base")
        return 1
    result = n * fact_log(n - 1, log)
    log.append(f"exit {n} -> {result}")
    return result

def run_fact_log():
    log = []
    value = fact_log(3, log)
    return value, log
```

1) What does `run_fact_log()` return?
2) Which happens first: all the `enter ...` messages, or some `exit ...` messages?

After you write your prediction as a comment, run it to check.

def fact_log(n, log):
    log.append(f"enter {n}")
    if n == 0:
        log.append("base")
        return 1
    result = n * fact_log(n - 1, log)
    log.append(f"exit {n} -> {result}")
    return result

def run_fact_log():
    log = []
    value = fact_log(3, log)
    return value, log

# Prediction (write BEFORE running):
# I predict run_fact_log() returns:
# (
#   value = ____ ,
#   log = [____]
# )

# Uncomment to check:
# print(run_fact_log())

In a recursive call like `result = n * fact_log(n-1, log)`, the multiplication can't happen until the recursive call returns.

So the function will keep appending `enter ...` until it hits the base case.

Only after the base case returns will the `exit ...` lines get appended (unwinding the call stack).

def fact_log(n, log):
    log.append(f"enter {n}")
    if n == 0:
        log.append("base")
        return 1
    result = n * fact_log(n - 1, log)
    log.append(f"exit {n} -> {result}")
    return result

def run_fact_log():
    log = []
    value = fact_log(3, log)
    return value, log

# run_fact_log() returns:
# (6, ['enter 3','enter 2','enter 1','enter 0','base','exit 1 -> 1','exit 2 -> 2','exit 3 -> 6'])

1. Trace Two Addition Processes (SICP Ex 1.9)

These two procedures both compute `a + b` using only `inc` and `dec`, but they generate different **process shapes**.

Trace by looking at the logged `(a, b)` pairs.

Tasks:
1) Predict the logs for `add_rec_log(4, 5)` and `add_iter_log(4, 5)` (write your prediction as comments).
2) Run the code to check.
3) Explain (in your own words): which one is a **linear recursive process** and which one is an **iterative process**?

```python
def inc(x):
    return x + 1

def dec(x):
    return x - 1
```

def inc(x):
    return x + 1

def dec(x):
    return x - 1

# Version 1 (like the first Scheme version):
# (+ a b) = if a==0: b else inc(+(dec(a), b))

def add_rec(a, b):
    if a == 0:
        return b
    return inc(add_rec(dec(a), b))

# Version 2 (like the second Scheme version):
# (+ a b) = if a==0: b else +(dec(a), inc(b))

def add_iter(a, b):
    if a == 0:
        return b
    return add_iter(dec(a), inc(b))

# Logging versions for tracing

def add_rec_log(a, b, log=None):
    if log is None:
        log = []
    log.append((a, b))
    if a == 0:
        return b, log
    value, log = add_rec_log(dec(a), b, log)
    return inc(value), log


def add_iter_log(a, b, log=None):
    if log is None:
        log = []
    log.append((a, b))
    if a == 0:
        return b, log
    return add_iter_log(dec(a), inc(b), log)

# Prediction (write BEFORE running):
# add_rec_log(4, 5) log: ______________________
# add_iter_log(4, 5) log: _____________________

# Uncomment to check:
# print(add_rec_log(4, 5))
# print(add_iter_log(4, 5))

In `add_rec`, the `inc(...)` happens AFTER the recursive call returns, so work is deferred (pending operations build up).

In `add_iter`, the state moves from (a,b) to (a-1,b+1) each call, with no pending work besides the next call.

Compare the logs: does `b` stay the same, or does it change each step?

def inc(x):
    return x + 1

def dec(x):
    return x - 1

def add_rec(a, b):
    if a == 0:
        return b
    return inc(add_rec(dec(a), b))

def add_iter(a, b):
    if a == 0:
        return b
    return add_iter(dec(a), inc(b))

def add_rec_log(a, b, log=None):
    if log is None:
        log = []
    log.append((a, b))
    if a == 0:
        return b, log
    value, log = add_rec_log(dec(a), b, log)
    return inc(value), log

def add_iter_log(a, b, log=None):
    if log is None:
        log = []
    log.append((a, b))
    if a == 0:
        return b, log
    return add_iter_log(dec(a), inc(b), log)

# add_rec_log(4,5) -> value 9, log [(4,5),(3,5),(2,5),(1,5),(0,5)] (linear recursive process)
# add_iter_log(4,5) -> value 9, log [(4,5),(3,6),(2,7),(1,8),(0,9)] (iterative process)

2. Recursive vs Iterative vs Memoized Recurrence (SICP Ex 1.11)

A function `f` is defined by:

- `f(n) = n` if `n < 3`
- `f(n) = f(n-1) + 2*f(n-2) + 3*f(n-3)` if `n >= 3`

Tasks (in order):

1) **Implement** `f_recursive(n)` using a direct recursive translation.
2) **Implement** `f_iter(n)` that computes the same values but using an **iterative process** (carry state explicitly).
3) **Extend**: implement `f_memo(n, memo=None)` using recursion + memoization (a dictionary cache).

Prediction checkpoint (do this before coding):
- Compute by hand: `f(3)`, `f(4)`, `f(5)`.

Your functions should all agree for the same input.

def f_recursive(n):
    """Direct recursion.

    f(n) = n                    if n < 3
    f(n) = f(n-1)+2f(n-2)+3f(n-3) if n >= 3
    """
    # YOUR CODE HERE
    raise NotImplementedError


def f_iter(n):
    """Iterative process (explicit state).

    Hint: keep three consecutive values so you can advance k -> k+1.
    One possible invariant after computing up through k:
      a = f(k), b = f(k-1), c = f(k-2)
    """
    # YOUR CODE HERE
    raise NotImplementedError


def f_memo(n, memo=None):
    """Recursion + memoization.

    Use a dict mapping int -> f(int).
    """
    # YOUR CODE HERE
    raise NotImplementedError


# Quick manual-check prints (optional)
# for i in range(10):
#     print(i, f_recursive(i), f_iter(i), f_memo(i))

For `f_iter`, start from the known base values: f(0)=0, f(1)=1, f(2)=2.

To advance from k to k+1 using (a,b,c) = (f(k), f(k-1), f(k-2)):
  next = a + 2*b + 3*c, then shift to (next, a, b).

For memoization, use the pattern:
  if memo is None: memo = {}
  if n in memo: return memo[n]
  compute and store memo[n] otherwise.

def f_recursive(n):
    if n < 3:
        return n
    return f_recursive(n - 1) + 2 * f_recursive(n - 2) + 3 * f_recursive(n - 3)


def f_iter(n):
    if n < 3:
        return n
    # a=f(2), b=f(1), c=f(0)
    a, b, c = 2, 1, 0
    k = 2
    while k < n:
        nxt = a + 2 * b + 3 * c  # f(k+1)
        a, b, c = nxt, a, b
        k += 1
    return a


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