末尾再帰を使用して出力リストを作成し、そのために、リストの先頭answer
に追加することで累積します。当然、逆にリストが作成されます。これを修正するためのいくつかのオプションがあります。1つは末尾再帰を捨てることです。
(define (square-list items)
(if (null? items)
nil
(cons (square (car items))
(square-list (cdr items)))))
その他、リストを処理する前にリストを逆にします。
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(cons (square (car things))
answer))))
(iter (reverse items) nil))
さらに別のオプション:要素をまとめるのではなく、最後に追加します。
(define (square-list items)
(define (iter things answer)
(if (null? things)
answer
(iter (cdr things)
(append answer
(list (square (car things)))))))
(iter items nil))
ただし、各オプションには独自のトレードオフがあります。
- 最初のオプションは末尾再帰ではありません(ただし、末尾再帰のモジュロ短所です)
- 2番目のオプションでは、1つの追加のトラバーサルと1つの追加のリストが必要です(これは、リストが逆になっている場合に発生します)
- 3番目のオプションは2次式です。これは、各追加操作がリストをトラバースして、最後に要素を追加するためです。
すべてを考慮すると、最良の末尾再帰オプションは2番目のオプションです。