Exercise 2.22. Louis Reasoner tries to rewrite the first square-list procedure of exercise 2.21 so that it evolves an iterative process:
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons (square (car things))
answer))))
(iter items nil))
Unfortunately, defining square-list this way produces the answer list in the reverse order of the one desired. Why?
Louis then tries to fix his bug by interchanging the arguments to cons:
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons answer
(square (car things))))))
(iter items nil))
This doesn’t work either. Explain.
观察 iter 过程
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons (square (car things))
answer))))
虽然在递归的时候，answer 参数的位置使用了正序的 (cons (square (car things)) answer) ，但每一次进入这个迭代式递归的时候，answer 参数位置都是将 things 的第一个放到当前的 answer 前面，这样到了下一层递归时，answer 就是 things 的前面几个元素。
如果以 (1 2 3 4 5) 为例，我们对 iter 进行 trace：
;;1 ]=> (trace iter)
;;Unspecified return value
;;1 ]=> (square-list '(1 2 3 4 5))
;; [Entering #[compound-procedure 3 iter]
;; Args: (1 2 3 4 5)
;; ()]
;; [Entering #[compound-procedure 3 iter]
;; Args: (2 3 4 5)
;; (1)]
;; [Entering #[compound-procedure 3 iter]
;; Args: (3 4 5)
;; (4 1)]
;; [Entering #[compound-procedure 3 iter]
;; Args: (4 5)
;; (9 4 1)]
;; [Entering #[compound-procedure 3 iter]
;; Args: (5)
;; (16 9 4 1)]
;; [Entering #[compound-procedure 3 iter]
;; Args: ()
;; (25 16 9 4 1)]
;; [(25 16 9 4 1)
;; <== #[compound-procedure 3 iter]
;; Args: ()
;; (25 16 9 4 1)]
;; [(25 16 9 4 1)
;; <== #[compound-procedure 3 iter]
;; Args: (5)
;; (16 9 4 1)]
;; [(25 16 9 4 1)
;; <== #[compound-procedure 3 iter]
;; Args: (4 5)
;; (9 4 1)]
;; [(25 16 9 4 1)
;; <== #[compound-procedure 3 iter]
;; Args: (3 4 5)
;; (4 1)]
;; [(25 16 9 4 1)
;; <== #[compound-procedure 3 iter]
;; Args: (2 3 4 5)
;; (1)]
;; [(25 16 9 4 1)
;; <== #[compound-procedure 3 iter]
;; Args: (1 2 3 4 5)
;; ()]
;;Value 4: (25 16 9 4 1)
事实上，当我们试着去看第 2 层的递归时，我们可以清楚地看到，answer 值是 '(1), 下一步就是把 things 的第一个元素 2 拿出来，平方之后放到 answer 的前面。
第二种方法产生的顺序是对的，但错误地使用了 cons 来组装 answer。下面是这个错误的方法产生的答案以及一个正确的迭代式的递归过程 square-list。
(define (square-list-2 items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons answer
(square (car things))))))
(iter items '()))
;1 ]=> (square-list-2 '(1 2 3 4 5))
;Value 7: (((((() . 1) . 4) . 9) . 16) . 25)
;;; the right way:
(define (square-list-right items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(append answer
(list (square (car things)))))))
(iter items '()))
;1 ]=> (square-list-right '(1 2 3 4 5))
;Value 8: (1 4 9 16 25)