Serendip

Web Studio

処理の一番最後に再帰呼び出しをして、その結果がそのまま現在の処理の結果として返されるパターンを末尾再帰と呼びます。
（プログラミングGauche p57）

プログラミングGauche

posted with amazlet at 08.11.14

Kahuaプロジェクト
オライリージャパン
売り上げランキング: 22775

Amazon.co.jp で詳細を見る

reverse を末尾再帰で書き直す。

非末尾再帰の reverse

(define (reverse lis)
  (if (not (pair? lis))
      lis
      (append2 (reverse (cdr lis)) (list (car lis)))))

(reverse '(1 2 3 4 5))
gosh> (5 4 3 2 1)

末尾再帰の reverse

(define (reverse lis)
  (define (iter lis result)
    (if (null? lis)
        result
        (iter (cdr lis) (cons (car lis) result))))
  (iter lis '()))

(reverse '(1 2 3 4 5))
gosh> (5 4 3 2 1)