[scheme][Gauche]末尾再帰

「プログラミングGauche」P.56～59 6.6 ２種類の再帰

 

末尾再帰とは

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

 

末尾再帰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」の末尾再帰の説明読んでみて、ようやくわかった。あとここ参考になった。