2種類の再帰でlengthを定義する

6.6の「Programing Gauche p54のappend2という手続き」ところね。

普通(？)の再帰

定義と書きくだしてみたやつを載せてみる。最後まで計算しないと全然計算が進んでいないことに注目。

(define (length lis)
  (if (null? lis)
      0
      (+ 1 (length (cdr lis)))))

(length '(1 2 3))

(+ 1 (length (cdr '(1 2 3))))

(+ 1 (length '(2 3)))

(+ 1 (+ 1 (length (cdr '(2 3)))))

(+ 1 (+ 1 (length '(3))))

(+ 1 (+ 1 (+ 1 (length (cdr '(3))))))

(+ 1 (+ 1 (+ 1 0)))

末尾再帰を使ったバージョン

ローカル手続きを使って定義するのだが、書きくだせなくなるので、とりあえず外でも定義しといた。まあ、この段階では問題ないからおk。理解優先。

(define (length lis)
  (define (length-rec lis n)
    (if (null? lis)
	n
	(length-rec (cdr lis) (+ n 1))))
  (length-rec lis 0)
  )

(define (length-rec lis n)
  (if (null? lis)
      n
      (length-rec (cdr lis) (+ n 1))))
(length-rec lis 0)


(length '(1 2 3))

(length-rec '(1 2 3) 0)

(length-rec (cdr '(1 2 3)) (+ 0 1))

(length-rec '(2 3) 1)

(length-rec (cdr '(2 3)) (+ 1 1))

(length-rec '(3) 2)

(length-rec (cdr '(3)) (+ 2 1))

(length-rec '() 3)

(length-rec '() 3)

3

最後まで行かなくってもちょびちょび計算できていることに注目。実質ループと手間は一緒と考えることができる。