Rekursion

[Reality]

Hi,
ich habe im Internet zufällig Quellcode zu einem Rekursionsprogramm gefunden.

Da ich nie damit etwas zu tun hatte, fällt mir das Nachvollziehen des Ergebnisses etwas schwer.

Hier der Quellcode:

public class Fib {
    public static int fib(int n) {
        if (n == 0 || n == 1)
            return n;
        return (fib(n-1) + fib(n-2));
    }

    public static void main(String[] args) {
        for (int i = 0; i < 36; i++)
            System.out.println("n=" + i + " => " + fib(i));
    }
}

Die Ausgabe ist folgende:

n=0 => 0
n=1 => 1
n=2 => 1
n=3 => 2
n=4 => 3
n=5 => 5
n=6 => 8
n=7 => 13
n=8 => 21
n=9 => 34
n=10 => 55
n=11 => 89
n=12 => 144
n=13 => 233
n=14 => 377
n=15 => 610
n=16 => 987
n=17 => 1597
n=18 => 2584
n=19 => 4181
n=20 => 6765
n=21 => 10946
n=22 => 17711
n=23 => 28657
n=24 => 46368
n=25 => 75025
n=26 => 121393
n=27 => 196418
n=28 => 317811
n=29 => 514229
n=30 => 832040
n=31 => 1346269
n=32 => 2178309
n=33 => 3524578
n=34 => 5702887
n=35 => 9227465

Wie man an der Ausgabe erkennen kann, setzt sich das Ergebnis eines jeden Durchlaufs, aus der Addition der letzten beiden Durchläufe zusammen.
Ich frage mich aber, weshalb z. B. bei n = 5 nicht solange iteriert wird, bis n entweder 1 oder 0 ist. Es scheint so, als ob z. B. bei n = 5, einfach einmal das Ergebnis des Durchlaufs von n = 4 genommen wird und einmal bei n = 3 und gut ist.
Die Sache ist eben die, dass bei der letzten Return-Anweisung dieselbe Funktion eben nochmals aufgerufen wird und das eben solange bis n entweder 1 oder 0 ist.

Irgendwie scheine ich auf dem Schlauch zu stehen! :bahnhof:

Liebe Grüße
Reality

 

[SlaterB]

fib(5) = fib(4) + fib(3)
nicht mehr und nicht weniger, das hat nix mit iterieren oder rekursieren zu tun,
das ist erstmal die mathematisch feste Definition,

um fib(4) und fib(3) zu berechnen werden natürlich rekursiv auch die unteren fib berechnet und zwar ziemlich oft sogar

 

[Reality]

um fib(4) und fib(3) zu berechnen werden natürlich rekursiv auch die unteren fib berechnet und zwar ziemlich oft sogar

Eben und die Ergebnisse der untersten beiden Durchläufe, wo die Abbruchbedingung erfüllt ist, sind 0 und 1.
Ich dachte, dass letztenendes immer nur das Ergebnis der Abbruchbedingung gilt, aber scheinbar ist das nicht der Fall.

Liebe Grüße
Reality

 

[Janus]

das kommt auf die art der rekursion an. in suchbäumen ist es z.b. häufig so, dass rekursion verwendet wird, um einen bestimmten knoten zu finden und auch nur der wird schlussendlich als ergebnis geliefert.

aber hier werden rekursiv explizit die ergebnisse der methode addiert. wie es die definition der fibonacci reihe halt erfordert.

um rekursion zu verstehen ist es hilfreich, sich jeden einzelnen schritt auf dem papier aufzuschreiben.

 

[Janus]

bei der fibonacci reihe geht das sogar noch recht simpel, wenn man das ganze einfach mal entfaltet:

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
=>
fib(5) = fib(3) + fib(2) + fib(2) + fib(1)
fib(5) = fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)
fib(5) = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)
fib(5) = 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
fib(5) = 5

 

[Reality]

Hey Janus,
danke für deine Aufzeichnungen! :-D
Jetzt ist mir das verständlich! :-D

Liebe Grüße
Reality