So far we haven’t used names that much for our λ calculus functions, mainly just with functions such as sqr. Recursion does require names, because we will call the functions multiple times. Here’s our function:

fact: (λn. (if (= n 1) 1 (* n (fact (- n 1))))

Let’s call (fact 3) and do a β reduction on 3:

(if (= 3 1) 1 (* 3 (fact (- 3 1)))

Clearly, (= 3 1) returns false, so we’re left with:

(* 3 (fact (- 3 1)))

Which becomes

(* 3 (fact 2))

Let’s do a β reduction on 2:

(* 3 (if (= 2 1) 1 (* 2 (fact (- 2 1))))

Okay, now this is starting to get complicated. It’s the same call we just had with (fact 3), but the expression is larger because we have the (* 3 … part too. Our test (= 2 1) returns false, so we just use the else part of the if to give us

(* 3 (* 2 (fact (- 2 1))))

We can reduce (- 2 1) to get

(* 3 (* 2 (fact 1)))

Now we do yet another β reduction to get:

(* 3 (* 2(if (= 1 1) 1 (* 1 (fact (- 1 1)))))

This time the if will return true, because (= 1 1) evaluates to true, so we have our simple case, which gives us:

(* 3 (* 2 1))

Suddenly this looks much simpler!

How about with ASTs?