再帰木エクスプローラー

単純な fib(10) は 177 回、fib(11) は 287 回の呼び出しを行うとツールは示しています。呼び出し回数の閉形式（一般項）を求めて証明してください。そして、一秒間に 10⁸ 回の呼び出しを処理できるコンピュータにおいて、単純なフィボナッチ数列が一秒間でどこまで計算できるか導き出してください。

1. それぞれの回数に 1 を足すと、178 と 288 になります。どちらも偶数であり、その半分は 89 と 144 です。これは F₁₁ と F₁₂ に一致します。したがって、F(1) = F(2) = 1 としたとき、推測される式は C(n) = 2F(n+1) − 1 となります。

   $$C(10)=177,C(11)=287⟹\frac{178}{2}=89=F_{11},\frac{288}{2}=144=F_{12}$$

2. この二倍という数字がどこから来るのかは、木を見るとわかります。すべての内部ノードは正確に二回の呼び出しを行い、葉は一度も呼び出しを行いません。したがって、L 個の葉を持つ木には L − 1 個の内部ノードがあり、ノードの総数は 2L − 1 となります。ツールによれば、n = 10 でのベースケースは 89 個です。だから 2 × 89 − 1 = 177 なのです。

   $$N=2L-1⟹2\times 89-1=177$$

3. まずはベースケースです。fib(0) と fib(1) は再帰せずに値を返すため、C(0) = C(1) = 1 となります。そして、2F(1) − 1 と 2F(2) − 1 はどちらも 1 に等しくなります。

   $$C(0)=C(1)=1,2F_1-1=2F_2-1=1$$

4. 次に帰納法のステップです。n − 1 と n − 2 においてこの式が成り立つと仮定します。n での呼び出しは、一つのノードとその下にある二つの部分木を足したものです。そこに含まれる二つのフィボナッチ数は、数列の定義そのものによって自然に一つにまとまります。n = 11 とすると 2 × 144 − 1 = 287。ツールが表示する値と完全に一致します。

   $$C(n)=1+C(n-1)+C(n-2)=1+(2F_n-1)+(2F_{n-1}-1)=2F_{n+1}-1$$

5. ここで木から離れましょう。ビネの公式は φ = 1.6180、|ψ| < 1 として F(m) = (φ^m − ψ^m)/√5 を与えます。そのため F(m) は φ^m/√5 を最も近い整数に丸めた値となり、C(n) ≈ 2φⁿ⁺¹/√5 と近似できます。一秒間に 10⁸ 回の速度であれば、一秒間でちょうど 10⁸ 回の呼び出しを行えます。これにより、φⁿ⁺¹ は 1.1180 × 10⁸ に固定されます。

   $$C(n)\approx \frac{2{\phi }^{n+1}}{\sqrt{5}}=10^8⟹{\phi }^{n+1}=\frac{10^8\sqrt{5}}{2}=1.1180\times 10^8$$

6. 対数をとります。ln(1.1180 × 10⁸) = 18.5323、ln φ = 0.4812 なので、n + 1 = 38.51 となり、n = 37.5 と求められます。端数分の呼び出しは完了しないため、切り捨てます。

   $$n+1=\frac{\ln \left(1.1180\times 10^8\right)}{\ln \phi }=\frac{18.5323}{0.4812}=38.51$$

1〜3段ずつ上る階段は各ノードで自分を三回呼び、ハノイの塔は二回呼びます。n=20の階段上り(3分岐)を読み込み、二つの木のどちらが速く育つかを求め、分岐数が指標としてどれだけ役に立つかを判断してください。

1. 漸化式は絵からではなく定義から読み取ります。ノード自身の呼び出しが1回、そこから n − 1、n − 2、n − 3 で3回、そして2以下なら再帰せずに返ります。

   $$C(n)=1+C(n-1)+C(n-2)+C(n-3),C(0)=C(1)=C(2)=1$$

2. 呼び出し回数が幾何級数的に増えると仮定して C(n) ≈ A xⁿ を代入します。両辺を x の n − 3 乗で割ると、先頭の1は低次の雑音として置き去りになり、三次方程式が残ります。その唯一の実根が 1.8392868、トリボナッチ定数です。

   $$C(n)\sim A{x}^n⟹x^3=x^2+x+1⟹x=1.8392868$$

3. 同じ手順を残る二つの定義に当てはめます。フィボナッチは n − 1 と n − 2 で自分を呼ぶので x² = x + 1 となり、根は φ = 1.6180340 です。ハノイは n − 1 で二回呼ぶので x = 2 となり、解くものは何もありません。

   $$\text{fib}:x^2=x+1\Rightarrow \phi =1.6180340;\text{hanoi}:C(n)=1+2C(n-1)\Rightarrow x=2$$

4. 信じる前に確かめます。n を29にして呼び出し回数のカードを読み、30にしてもう一度読み、割ります。階段は1.83929、フィボナッチは1.61803、ハノイはちょうど2。三つとも小数第五位まで一致します。

   $$\frac{C(30)}{C(29)}:\frac{56,843,233}{30,905,041}=1.83929,\frac{2,692,537}{1,664,079}=1.61803,\frac{2^{31}-1}{2^{30}-1}=2.00000$$

5. 根が教えてくれないのは回数そのものです。1.8393²⁰ は196,331ですが、カードの表示は128,287。前に0.65という係数が付いています。ハノイの呼び出しはちょうど 2ⁿ⁺¹ − 1 で、係数は2です。ベースケースがこの定数を決め、漸化式が根を決めます。そして最後に勝敗を決めるのは根だけです。

   $$1.8393^{20}=196,331\text{against}128,287⟹A=0.6534;\text{hanoi}:C(n)=2^{n+1}-1,A=2$$

6. その最後は、ここではすぐに訪れます。n = 20 でハノイの呼び出しは階段の16.3倍、n = 30 では37.8倍になります。この比は8.3ステップごとに倍になります。ln 2 を ln(2 ÷ 1.8393) で割ると8.27だからです。

   $$\frac{2^{21}-1}{128,287}=16.3,\frac{2^{31}-1}{56,843,233}=37.8,\frac{\ln 2}{\ln (2/1.8393)}=8.27$$