Rekursionsbaum-Explorer

Das Tool sagt, naives fib(10) führt 177 Aufrufe durch und fib(11) benötigt 287. Finde die geschlossene Form für die Aufrufzahl und beweise sie. Berechne anschließend, wie weit naives Fibonacci in einer Sekunde auf einer Maschine kommt, die 10⁸ Aufrufe pro Sekunde bewältigt.

1. Addiere eins zu jedem Wert, das ergibt 178 und 288. Beide sind gerade, ihre Hälften lauten 89 und 144. Das sind exakt F₁₁ und F₁₂. Die Vermutung lautet also C(n) = 2F(n+1) − 1, mit F(1) = F(2) = 1.

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

2. Der Baum erklärt die Herkunft der Verdopplung. Jeder innere Knoten macht exakt zwei Aufrufe, jedes Blatt macht gar keinen. Folglich besitzt ein Baum mit L Blättern genau L − 1 innere Knoten und damit insgesamt 2L − 1 Knoten. Das Tool meldet 89 Basisfälle bei n = 10, und 2 × 89 − 1 = 177.

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

3. Zuerst die Basisfälle. fib(0) und fib(1) enden ohne Rekursion. Es gilt also C(0) = C(1) = 1, und sowohl 2F(1) − 1 als auch 2F(2) − 1 ergeben 1.

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

4. Nun zum Induktionsschritt. Nimm die Formel für n − 1 und für n − 2 als gegeben an. Der Aufruf bei n ist ein Knoten plus seine zwei Teilbäume. Die beiden Fibonacci-Zahlen darunter fallen durch die Definition der Folge selbst zusammen. Setzt du n = 11, ergibt das 2 × 144 − 1 = 287. Das entspricht exakt der Ausgabe des Tools.

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

5. Lass den Baum hier hinter dir. Die Formel von Binet liefert F(m) = (φ^m − ψ^m)/√5 mit φ = 1,6180 und |ψ| < 1. F(m) ist also φ^m/√5, gerundet auf die nächste Ganzzahl. Daraus folgt C(n) ≈ 2φⁿ⁺¹/√5. Eine Sekunde bei 10⁸ Aufrufen pro Sekunde liefert dir genau 10⁸ Aufrufe. Das fixiert φⁿ⁺¹ auf 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. Wende den Logarithmus an. ln(1,1180 × 10⁸) = 18,5323 und ln φ = 0,4812. Daraus folgt n + 1 = 38,51 und n = 37,5. Runde ab, denn ein bruchteilhafter Aufruf wird nicht fertiggestellt.

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

Die Dreierschritt-Treppe ruft sich an jedem Knoten dreimal selbst auf, die Türme von Hanoi zweimal. Lade Treppe 20, drei Zweige, finde heraus, welcher der beiden Bäume schneller wächst, und entscheide, was der Verzweigungsgrad als Faustregel taugt.

1. Lies die Rekursionsgleichung aus der Definition ab, nicht aus dem Bild. Ein Aufruf für den Knoten selbst, dann drei weitere bei n − 1, n − 2 und n − 3, und alles bei 2 oder darunter kehrt zurück, ohne erneut zu rekursieren.

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

2. Nimm an, die Anzahl wächst geometrisch, C(n) ≈ A xⁿ, und setz das ein. Teile alles durch x hoch n − 3, die führende 1 bleibt als Rauschen niedrigerer Ordnung zurück, und übrig bleibt eine kubische Gleichung. Ihre einzige reelle Wurzel ist 1,8392868, die Tribonacci-Konstante.

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

3. Dasselbe Rezept auf die beiden anderen Definitionen. Fibonacci ruft sich bei n − 1 und n − 2 auf, also x² = x + 1 mit der Wurzel φ = 1,6180340. Hanoi ruft sich zweimal bei n − 1 auf, also x = 2, und es gibt nichts zu lösen.

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

4. Prüfe es, statt es zu glauben. Setz n auf 29, lies die Karte mit den ausgeführten Aufrufen ab, setz n auf 30, lies erneut ab, teile. Die Treppe gibt 1,83929, Fibonacci 1,61803, Hanoi genau 2. Fünf Nachkommastellen bei allen dreien.

   $$\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. Was die Wurzel dir nicht gibt, ist die Anzahl. 1,8393²⁰ ist 196.331, während die Karte 128.287 zeigt; davor sitzt also ein Faktor 0,65. Hanois Aufrufe sind exakt 2ⁿ⁺¹ − 1, ein Faktor 2. Die Basisfälle legen diese Konstante fest, die Rekursionsgleichung legt die Wurzel fest, und nur die Wurzel entscheidet, wer am Ende gewinnt.

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

6. Das Ende kommt hier schnell. Bei n = 20 macht Hanoi 16,3-mal so viele Aufrufe wie die Treppe, bei n = 30 sind es 37,8-mal so viele. Das Verhältnis verdoppelt sich alle 8,3 Schritte, denn ln 2 geteilt durch ln(2 ÷ 1,8393) ist 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$$