数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.2.2)

minghaiさんによるSICP全訳を読んでいます。

過去記事
数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.1) - エンジニアをリングする
数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.2.1) - エンジニアをリングする

1.2.2 木再帰

前回は「線形再帰と反復」について学びました。
今回は何でしょうか。

もう 1 つの演算の一般的パターンはtree recursion(木再帰) と呼ばれます。例として、フィボナッチ数の計算について考えてみましょう。各数値は先行する 2 つの数の和となります。

フィボナッチ数きたー！

定義

Fib(n) = 0                     if n = 0
Fib(n) = 1                     if n = 1
Fib(n) = Fib(n-1) + Fib(n-2)   otherwise.

（このへんの数学っぽい記述は結城先生の本とか読んで慣れました。）

Schemeでの記述

(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1))
                   (fib (- n 2))))))

この実装方法の問題点

• (fib n)を求める処理は(+ (fib n-1) (fib n-2))になるが、(fib n-1)の計算の中に(fib n-2)も含まれるため、(fib n-2)の計算がまるまる重複する
• 自身の中で自身を2回呼び出すので、ステップ数がnに対し指数関数的に増加する

ただ、「定義をストレートに翻訳した処理になっているので直感的にわかりやすい」という長所もある。

注意点。
「ステップ数は指数関数的に増加するが、必要な記憶域は線形に増加する」ということ。

従ってプロセスは入力に伴ない指数関数的に増加するステップ数を要します。一方で要求される記憶域は入力に対し線形にしか増加しません。なぜなら計算過程の任意のポイントにおいて、木の中のどのノードが上にあるのかのみ追跡する必要があるためです。 一般的に、木再帰プロセスにおいて必要とされるステップ数は木の中のノードの数に比例します。必要とされる記憶域は木の最大の深さに対して比例します。

※上記の図がわかりやすかったのでこちらも引用させていただきました。

• プロセス（自身の実行回数）は指数関数的に増加＝木の中のノードの数に比例
• 必要な記憶域は線形に増加＝木の最大の深さに比例

なぜプロセスが指数関数的なのに必要な記憶域の増加は線形なのかちょっとひっかかったのですが、たとえば(fib 5)の場合、「必要になる(fib 4)と(fib 3)を同時に計算するわけではない」ということに思い至り納得しました。
確かに、覚えておかなければいけないことは「どこまで深く潜ったか」なので木の最大の深さと同じになりますね。
nが1増えれば深さも1増えるという線形の増加です。
前回やった「線形再帰プロセス」と同じですね。

ただ、線形再帰プロセスはプロセスも線形の増加ですが、木再帰の場合はプロセスが線形でなく指数関数的に増加するということですね。
自身の中で自身を２回呼び出していくので、２×２×２×・・・というのがイメージしやすいです。

次は同じフィボナッチ数を求める関数の反復プロセスでの実装。

(define (fib n)
    (fib-iter 1 0 n))
(define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))

fib-iterの最後の処理がfib-iter、末尾再帰になっているので、反復プロセスに最適化される。
線形反復プロセスなので、記憶域は一定、プロセスは線形の増加です。
さっきの木再帰と比べると、nが大きくなった場合にかなり効率が違いますね。

これより木再帰プロセスが役に立たないと結論づけるべきではありません。数値ではなく階層構造のデータを操作するプロセスを考えた場合、木再帰は自然で強力なツールです。しかし、例え数値演算においても木再帰はプログラムの設計と理解を手助けするのに役立ちます。例えば最初の fib 手続は 2 つ目に比べてとても非効率ですが、より直感的でフィボナッチ数列の定義と Lisp 翻訳の違いは大差がありません。

例：両替方法を数える

次の問題について考えてみて下さい：$1.00 を両替するにはいくつの方法があるでしょうか? 50 セント、25 セント、10 セント、5 セント、1 セント硬貨があります。より一般的に、任意の量の金額に対して両替方法がいくつ存在するか計算する手続を書くことができますか?

おー数学の問題っぽい！！
これ確かプログラマの数学に同じ解き方の問題がありました。
（5/8追記：数学ガールだったようです。）

たとえば、1000円札を500円・100円・50円・10円・5円・1円で両替する方法の数は、
500円を使う場合と使わない場合にわけられるので

1000円札を100円・50円・10円・5円・1円で両替する方法の数
＋
500円を500円・100円・50円・10円・5円・1円で両替する方法の数（残りの500円は常に500円玉になっているとみなす）

で、求められるそうです。

確かによくよく考えればなるほどですね。
こういう考え方ができないんですよね・・・
だから勉強しているんですけど。。。

この解き方だと、

• 1000円の両替の仕方を２通りにわけてそれを足すことで求めている
• なおかつその２通りの求め方それぞれがどんどん縮小していくので最終的な答えにたどり着ける

なのでまさしく木再帰で求められるんですね。

コードも載ってるんですが、かなりこんがらがるので省略・・・。

課題1.11 関数f

ex_1_11.scm
関数fを再帰プロセスと反復プロセスでそれぞれ定義する。
再帰プロセスは書けたけど反復プロセスわからなかった・・・紙に書いたりしたけど袋小路でした。
カウンタを使うのと、上から減らしていくんじゃなくて下から増やしていくのかなというのはなんとなく思ったのですが・・・
ずらしていくのをうまく使わないといけないんですね。
解答見てもあんまりすっきり感ないので完全に降参です。

課題1.12 パスカルの三角形の要素を求める

わからない・・・
まずどういう出力が期待されてるのかもわからない・・・改行なしで1から順番に出していけばいいのか。。
そうだとしても結局どう書けばいいかはわからない・・・
悔しいのでRubyで書いた！！できた！！each_cons便利！！！
ex_1_12.rb

課題1.13 Fib(n)がφⁿ/√5に最も近いことの証明

Fib(n)がφⁿ/√5に最も近い整数であることを証明せよ。φ=(1+√5)/2とする。
ヒント：Ψ=(1-√5)/2 と置く。帰納法とフィボナッチ数の定義を用いてFib(n)=(φⁿ-Ψⁿ)/√5であることを証明せよ。

うわー！！たすけてーー！！！
無謀にも途中までやってみましたがやっぱりむりでした・・・
ex_1_13.scm

しかもこれをどうやってSchemeで証明するんだろうか・・・

1.2.2 木再帰 終えて

課題がだんだん数学的になってきて数学力ない私にはつらくなってきました。。。
でも線形再帰プロセスと木再帰のプロセス増加量の違いとか、面白いです。
数学的な話も、できないんですけど、嫌いじゃないです。
今後できるようになったら課題更新したいです。

しかし一人だと一人分の頭しかないのでつらい・・・
仲間か先生がほしいです(T∀T)