再帰でループします。

好きな数字を心に思ってください。その数字に3を足します。さらに2をかけます。今度は4を足してください。2で割ります。最後に、最初に思った数字を引いてください。

さて。好きな数字を思ってもらいました。さらに計算をしたので、その結果は誰にも分かりません。それでは、最後に出た数字を、しっかりと思い浮かべてください。しっかりと。

分かりました。

その数字は、「5」です。

というわけで、サイキックなid:shunsukです。今日は、再帰ックなお話をします。再帰を使うと、繰り返しの処理を行うことができます。それが、最初は難しい。Schemeの最初のつまずきポイントだと思います。つまずき聡です。

nの階乗を求めるプログラムです。fact関数を定義していますが、その中で自分自身（fact関数）を読んでいます。これを再帰と言います。

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(fact 5)
;=> 120

(* 5 (* 4 (* 3 (* 2 1))))がイメージできますか？難しいですね。Schemeにはdoという繰り返し構文もあります。

(define (fact n)
  (do ((m n (- m 1)) (x n (* x (- m 1))))
    ((= m 1) x)))

(fact 5)
;=> 120

mをnで初期化して、処理ごとに(- m 1)しています。また、xをnで初期化して、(* x (- m 1))しています。そして、(= m 1)になったらxを返しています。doの方が使いづらいでしょ？そこで、Schemeでは再帰が多用されます。

もう一度、再帰のプログラムに戻ってみましょう。

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

(fact 5)
;=> 120

関数の中で関数を呼ぶと、関数呼び出しの履歴が積み上げられて（スタックされて）いきます。そうすると、パフォーマンスが低下するのです。ここで、fact関数で最後に評価されるのは、nと(fact (- n 1))との掛け算です。実は、最後に再帰関数呼び出しを行うと、スタックされずに、単純にジャンプするようになる裏ワザがあるのです。と言っても、誰もが知っている裏ワザなので、むしろ表ワザです。

下のコードでは、fact-iter関数の最後がfact-iter関数の呼び出しになっています。

(define (fact n)
  (fact-iter n n))

(define (fact-iter n x)
  (if (= n 1)
      x
      (let ((next-n (- n 1)))
	(fact-iter next-n (* x next-n)))))

(fact 5)
;=> 120

これにより、効率よく処理を行うことができるようになります。これを、末尾再帰と言います。ラーメン、つけ麺、末尾再帰。

2つの関数に別れてしまいましたが、1つにまとめることもできます。loop構文を使います。mにnの値をセット。xにnの値をセット。

(define (fact n)
  (let loop((m n) (x n))
    (if (= m 1)                    
        x
        (let ((next-m (- m 1)))
          (loop next-m (* x next-m))))))

(fact 5)
;=> 120

下のような書き方もできます。letrecはletのパワーアップバージョンです。iterの中でiterを呼べるのがポイント。

(define (fact n)
  (letrec ((iter (lambda (m x)
		   (if (= m 1)
		       x
		       (let ((next-m (- m 1)))
			 (iter next-m (* x next-m)))))))
    (iter n n)))

(fact 5)
;=> 120

というカンジで、再帰のプログラムを載せてみました。解ってる人にはカンタンすぎて、解らない人にはサッパリ解らない。愛しいけれど憎いヤツです。

9LISP 003で、再帰までやるかどうか分かりませんが、もっと解りやすい解説ができるように勉強してきますね。9LISP 003で、再帰までやるかどうか分かりませんが、もっと解りやすい解説ができるように勉強してきますね。繰り返し処理してみました。