The true meaning of recursion in the SICP book

Questions & Answers
1

In chapter 1 subchapter 1.1.3 there is the sentence

"First, observe that the first step dictates that in order to accomplish the evaluation process for a combination we must first perform the evaluation process on each element of the combination. Thus, the evaluation rule is recursive in nature; that is, it includes, as one of its steps, the need to invoke the rule itself."

shortly after this sentence in the book an example is given (* (+ 2 (* 4 6)) (+ 3 5 7)). The above example looks like a procedure calling another procedure rather than a procedure calling itself. My question is, I don't see any recursion in that example if the recursion in question is recursion in the general sense. Is there a special meaning of recursion in racket or other lisp dialects?

2

I think also in the Lisp/Racket context, "recursion" is usually understood as a function calling itself or functions calling each other.

On the other hand, in the paragraph you quoted, "recursive" means that to evaluate a function call, all the inner calls must be evaluated first. To evaluate the inner calls, their inner calls must be evaluated, and so on. That is, the innermost expressions are evaluated first and the outermost expression last.

So "recursion" as used in the SICP paragraph isn't the "true" meaning, but an alternative meaning. You could also say that the usual definition of "recursion" is a special case of "recursion" as used in the SICP paragraph.

1 Like
3

thanks for the answer!

1 Like
4

The book says the "evaluation rule" is recursive. That is, the rule used to evaluate the example expression is recursive, not the expression itself. Later, much later, in the book, you'll see how to define the "evaluation rule" in form of a little interpreter. Here you will see concretely how the evaluation rule is recursive.

5 Likes
5

got it! thanks for the answer!

6

can you give me the page number that shows how to define the evaluation rule in the book? i tried to look for it in the book, but i haven't found it yet. some people have their own assumptions about the recursion in question so i'm confused by people's answers, until now i'm still trying to understand the meaning of recursion from the sentence above. thanks.

7

I assume the SICP section @soegaard means is this:

4.1 The Metacircular Evaluator .

If you're referring to me: I agree with what @soegaard wrote here. I missed the detail that the sentence from the book was referring to the evaluation rule, not the evaluated expression.

So there's actually no contradiction between what the book says and the common definition of recursion.

1 Like
8

Wrt the recursive evaluation rule see chapter 4.
The core of eval looks like this:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type -- EVAL" exp))))
1 Like
9

i want to clarify that i asked this question on several websites on the internet, one of which was on this website. some people answered similar to the answer here, some answered like you did and some answered like @soegaard. and the different answers confused me before.

i just read the reference, now i quite understand the concept. thanks for helping!

1 Like