Iterative Factorial
Your recursive factorial works. But trace what happens when it computes factorial(5):
factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * (1 * factorial(0)))))
5 * (4 * (3 * (2 * (1 * 1))))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120The computation expands outward, then contracts. Each call defers a multiplication — the interpreter has to remember all those pending operations. This is a recursive process.
But there is another way. Instead of deferring work, carry a running product as you go:
fact-iter(5, 1)
fact-iter(4, 5)
fact-iter(3, 20)
fact-iter(2, 60)
fact-iter(1, 120)
fact-iter(0, 120)
120No expansion. At every step, the full state of the computation is captured in two numbers: n and acc. This is an iterative process — even though the function is still recursive.
NOTE
Both versions use a function that calls itself. The difference is not in the syntax but in the shape of the computation. A recursive process builds up deferred operations. An iterative process carries all its state in its arguments.
Define fact-iter — a curried function that takes n, then acc. If n is 0, return acc. Otherwise, call fact-iter with n - 1 and n * acc.
Then define factorial as a wrapper that calls fact-iter with an initial accumulator of 1.