Recursion

So far you’ve built an evaluator that handles numbers, operators, variables, functions, conditionals, and currying. Now it’s 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.

Let’s find out.

---

What You’ll Do

1. First, you’ll write a recursive factorial in our language
2. Then, you’ll discover a hidden bug in how our evaluator handles environments — and fix it