4.4 Evaluating recursive applications

Evaluating an application of a recursive procedure follows the evaluation rules just like any other expression evaluation. It may be confusing, however, to see that this works because of the apparent circularity of the procedure definition.

Here, we show in detail the evaluation steps for evaluating (factorial 2). The evaluation and application rules refer to the rules summary in Section 3.8. We first show the complete evaluation following the substitution model evaluation rules in full gory detail, and later review a subset showing the most revealing steps. Stepping through even a fairly simple evaluation using the evaluation rules is quite tedious, and not something humans should do very often (that’s why we have computers!) but instructive to do once to understand exactly how an expression is evaluated.

The evaluation rule for an application expression does not specify the order in which the subexpressions are evaluated. A Scheme interpreter is free to evaluate them in any order. Here, we choose to evaluate the subexpressions in the order that is most readable. The value produced by an evaluation does not depend on the order in which the subexpressions are evaluated.1

In the evaluation steps, we use typewriter font for uninterpreted Scheme expressions and sans-serif font to show values. So, 2 represents the Scheme expression that evaluates to the number 2.

The key to evaluating recursive procedure applications is if special evaluation rule. If the if expression were evaluated like a regular application all subexpressions would be evaluated, and the alternative expression containing the recursive call would never finish evaluating! Since the evaluation rule for if evaluates the predicate expression first and does not evaluate the alternative expression when the predicate expression is true, the circularity in the definition ends when the predicate expression evaluates to true. This is the base case. In the example, this is the base case where (= n 0) evaluates to true and instead of producing another recursive call it evaluates to 1.

The Evaluation Stack. The structure of the evaluation is clearer from just the most revealing steps:

(1) (factorial 2)

(17)   (* 2 (factorial 1))

(31)    (* 2 (* 1 (factorial 0)))

(40)    (* 2 (* 1 1))

(41)  (* 2 1)


Step 1 starts evaluating (factorial 2). The result is found in Step 42. To evaluate (factorial 2), we follow the evaluation rules, eventually reaching the body expression of the if expression in the factorial definition in Step 17. Evaluating this expression requires evaluating the (factorial 1) subexpression. At Step 17, the first evaluation is in progress, but to complete it we need the value resulting from the second recursive application.

Evaluating the second application results in the body expression, (* 1 (factorial 0)), shown for Step 31. At this point, the evaluation of (factorial 2) is stuck in Evaluation Rule 3, waiting for the value of (factorial 1) subexpression. The evaluation of the (factorial 1) application leads to the (factorial 0) subexpression, which must be evaluated before the (factorial 1) evaluation can complete.

In Step 40, the (factorial 0) subexpression evaluation has completed and produced the value 1. Now, the (factorial 1) evaluation can complete, producing 1 as shown in Step 41. Once the (factorial 1) evaluation completes, all the subexpressions needed to evaluate the expression in Step 17 are now evaluated, and the evaluation completes in Step 42.

Each recursive application can be tracked using a stack, similarly to processing RTN subnetworks (Section 2.3). A stack has the property that the first item pushed on the stack will be the last item removed—all the items pushed on top of this one must be removed before this item can be removed. For application evaluations, the elements on the stack are expressions to evaluate. To finish evaluating the first expression, all of its component subexpressions must be evaluated. Hence, the first application evaluation started is the last one to finish.recursive definition`)

Exercise 4.46. This exercise tests your understanding of the (factorial 2) evaluation.

  1. In step 5, the second part of the application evaluation rule, Rule 3(b), is used. In which step does this evaluation rule complete?

  2. In step 11, the first part of the application evaluation rule, Rule 3(a), is used. In which step is the following use of Rule 3(b) started?

  3. In step 25, the first part of the application evaluation rule, Rule 3(a), is used. In which step is the following use of Rule 3(b) started?

  4. To evaluate (factorial 3), how many times would Evaluation Rule 2 be used to evaluate the name factorial?

  5. $\left[\star \right]$To evaluate (factorial n) for any positive integer n, how many times would Evaluation Rule 2 be used to evaluate the name factorial?

Exercise 4.47. For which input values n will an evaluation of (factorial n) eventually reach a value? For values where the evaluation is guaranteed to finish, make a convincing argument why it must finish. For values where the evaluation would not finish, explain why.

  1. This is only true for the subset of Scheme we have defined so far. Once we introduce side effects and mutation, it is no longer the case, and expressions can produce different results depending on the order in which they are evaluated.