どうやらSICP第1章の趣旨を勘違いしていたっぽい。しかも2重に。
いただいたコメントで紹介されている記事（Scheme:末尾再帰で木をトラバース）を読んで気が付いた一つ目の勘違いは、末尾再帰で書くことにより必ずしも効率がよくなるわけではないということ。それを意識してSICP第1章を読み直すと、確かにそんなことは書いてない。それどころか、式の処理モデルとインタプリタの実装とは別のはなしだって強調されてる。
もう一つの勘違いは、末尾再帰とiterativeなプロセスの混同。正確にいうと混同していたわけではなく、末尾再帰で書くことでiterativeに書いたことにもなると思いこんでいた。どっちも、勘違いの程度としてはたいしてかわらないので、いいわけにもならない。
結局、SICP第1章の目的は計算プロセスをより深く理解することであって、coolなプログラムを書くことではないんだろう。

以上を踏まえて、両替問題のiterativeバージョンに再挑戦。アイデアは、前回の項和を求めるプロシージャをiterativeに書こうというもの。このアイデアそのものは同じだけど、すこし頭がすっきりしたので問題がクリアに見えるようになった。

まず、一般に f の項和を求めるプロシージャが次のようにiterativeに書けることを確認。いちおう末尾再帰になっている。

;; Iterative sum
(define (sum f a z)
  (define (sum-iter i summed)
    (if (> i z)
        summed
        (sum-iter (+ i 1) (+ summed (f i)))))
  (sum-iter a 0))

(sum (lambda (x) x) 1 10)
=> 55

これを、先日の両替問題におけるsumに応用すると、次のようになる。

;; change coin iterative
(define (d k)
  (cond ((= k 1) 1)
        ((= k 2) 5)
        ((= k 3) 10)
        ((= k 4) 25)
        ((= k 5) 50)))

(define (cc-iter a k)
  (define (sum i summed)
    (if (= i (- k 1))
        summed
        (sum (+ i 1)
             (+ summed (cc-iter (- a (d (- k i))) (- k i))))))
  (cond ((< a 0) 0)
        ((= k 1) 1)
        (else (sum 0 1))))

(define (count-change-iter a)
  (cc-iter a 5))

(count-change-iter 100)
=> 292

これは、末尾再帰ではない。けど、iterative （だよね？）。