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
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,
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
The Evaluation Stack. The structure of the evaluation is clearer from just the most revealing steps:
(* 2 (factorial 1))
(* 2 (* 1 (factorial 0)))
(* 2 (* 1 1))
(* 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
(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,
(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
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
1 as shown in Step 41. Once the
evaluation completes, all the subexpressions needed to evaluate the
expression in Step 17 are now evaluated, and the evaluation completes in
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.
In step 5, the second part of the application evaluation rule, Rule 3(b), is used. In which step does this evaluation rule complete?
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?
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?
(factorial 3), how many times would Evaluation Rule 2 be used to evaluate the name
$\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
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
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. ↩