2009/01/26

[scheme][Gauche]末尾再帰

プログラミングGauche」P.56~59 6.6 2種類の再帰

 

末尾再帰とは

処理の一番最後に再帰呼び出しをして、その結果がそのまま現在の処理の結果として返されるパターンを末尾再帰と呼びます

 

末尾再帰length

;; length tail-recursive
(define (length3 ls)
  (define (len-iter ls n)
    (if (null? ls)
    n
    (len-iter (cdr ls)(+ n 1))))
  (len-iter ls 0))

(length3 '(1 2 3 4 5)) ;; => 5
(length3 '()) ;; => 0
(length3 (cons 1 2)) ;; => ERROR: pair required, but got 2

 

末尾再帰reverse

;; tail-recursive reverse
(define (reverse ls)
  (define (reverse-iter ls ret)
    (if (null? ls)
    ret
    (reverse-iter (cdr ls)(cons (car ls) ret))))
  (reverse-iter ls '()))

(reverse '(1 2 3 4 5)) ;; => (5 4 3 2 1)
(reverse '()) ;; => ()

 

 

SICPの末尾再帰のところ読んでもあまりピンとこなかったんだけど、「プログラミングGauche」の末尾再帰の説明読んでみて、ようやくわかった。あとここ参考になった。

0 件のコメント:

コメントを投稿