2010-05-21

http://anond.hatelabo.jp/20100521003404

うん。できない。末尾再帰最適化ができる形式の階乗は、

n! = fact_iter(n,1)

fact_iter(0, acc) = acc
fact_iter(n, acc) = fact_iter(n-1, acc*n)

だ。

schemeで書くなら

(define (fact n)
  (define (iter n acc)
    (if (= n 0) acc (iter (- n 1) (* n acc))))
  (iter n 1))

だな。

そのへん興味あるならSICP読むといいよ。

記事への反応 -
  • あれ?

    階乗の計算式 n! = n * (n-1)! (n>0の場合) 1 (n=0の場合) をそのままプログラムにしたら末尾再帰の最適化はできないよな?

    • http://anond.hatelabo.jp/20100521003404

      うん。できない。末尾再帰の最適化ができる形式の階乗は、 n! = fact_iter(n,1)fact_iter(0, acc) = accfact_iter(n, acc) = fact_iter(n-1, acc*n) だ。 schemeで書くなら (define (fact n) (define (iter n acc) (if (= n 0) ac...

記事への反応(ブックマークコメント)

アーカイブ ヘルプ
ログイン ユーザー登録
ようこそ ゲスト さん