Recursion

Your evaluator now has closures — each function remembers the environment where it was defined. Time for something new: a function that calls itself.

---

What is Recursion?

Consider factorial:

• factorial(0) = 1
• factorial(3) = 3 * 2 * 1 = 6
• factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

The pattern: multiply n by the factorial of n - 1, until you reach 0.

In JavaScript:

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

In Python:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

This works because the function is stored by name before it’s called. When the body says factorial(n - 1), it looks up factorial in the environment, finds itself, and calls itself with a smaller input.

---

Does It Work in Our Language?

Our evaluator stores functions by name using define. When a function’s body references its own name, the evaluator looks it up with get and finds the function. So recursion should just work.

---

What You’ll Do

1. Write a recursive factorial in our language — no changes to the evaluator, just a program that calls itself
2. Rewrite factorial as an iterative process — same recursive function, but carrying all the state in the arguments instead of deferring work