Hilfe bei der Logik

[ITAMY]

Ich verstehe es einfach nicht. 0 1 1 2 krieg ich ja noch raus, aber wie kommt der nun auf 3 5 8 13 ..
Ich kann dem irgendwie nicht folgen, deshalb bitte ich um Hilfe. Danke euch.

public class Aufg6{
    public static void main(String[]args){
        int n = 8;
        for(int i=0;i<n;++i){
            System.out.print(doit(i)+" ");
        }
    }
    public static long doit(long n){
        return (n<2) ? n : doit(n-1) + doit(n-2);
    }
}

Output:
0 1 1 2 3 5 8 13

 

[JCODA]

Was wird denn gerechnet, bzw aufgerufen, wenn du doit(5) aufrufst?

 

[kneitzel]

Liegt dein Verständnis-Problem eventuell einfach nur am conditional operator? Die Methode doit kann man umschreiben:

    public static long doit(long n){
        // Abbruchbedingung der Rekursion
        if (n<2) return n;
        
        // Rekursive Berechnung
        return doit(n-1) + doit(n-2);
    }

Habe sogar noch zwei Kommentare hinzugefügt, damit dieser Standard-Aufbau einer Rekursion erläutert wird mit Abbruchbedingung und der eigentlichen rekursiven Berechnung.

 

[ITAMY]

Liegt dein Verständnis-Problem eventuell einfach nur am conditional operator? Die Methode doit kann man umschreiben:

    public static long doit(long n){
        // Abbruchbedingung der Rekursion
        if (n<2) return n;
       
        // Rekursive Berechnung
        return doit(n-1) + doit(n-2);
    }

Habe sogar noch zwei Kommentare hinzugefügt, damit dieser Standard-Aufbau einer Rekursion erläutert wird mit Abbruchbedingung und der eigentlichen rekursiven Berechnung.

Nein, ich hätte gern die einzelnen schritte, was da genau passiert. Das mit dem operator und das es rekursiv ist, damit ist kein Problem.
Ich kann nicht nachvollziehen, wie man auf 13 kommt.

 

[ITAMY]

.

 

[ITAMY]

Was wird denn gerechnet, bzw aufgerufen, wenn du doit(5) aufrufst?

Ich hab keine ahnung

 

[Javinner]

Nein, ich hätte gern die einzelnen schritte, was da genau passiert.

public class RecDemo
{

    public static int x = 0; //<<<

    public static void main(String[] args)
    {
        int n = 8;
        for (int i = 0; i < n; ++i)
        {
            System.out.print(doit(i) + " ");
        }
    }

    public static long doit(long n)
    {
        System.out.println("Here Nr.: " + x); //<<<
        x++;
        return (n < 2) ? n : doit(n - 1) + doit(n - 2);
    }

}

 

[Meniskusschaden]

Was wird denn gerechnet, bzw aufgerufen, wenn du doit(5) aufrufst?

Ich hab keine ahnung

Manchmal hilft es für das Verständnis, wenn man die aufgelösten Rekursionen einfach aufschreibt. Hier z.B. für doit(4):

doit(4) = doit(3)                     + doit(2)
        = doit(2)           + doit(1) + doit(1) + doit(0)
        = doit(1) + doit(0) + 1       + 1       + 0
        = 1       + 0       + 2
        = 3

 

[Javinner]

@Meniskusschaden Das stimmt schon. Wie hier jedoch der Fall, wird es ab der Zahl 5 sehr unübersichtlich und wenn man weiß, wie man sich hilft, ist es doch schon eine Ecke leichter zu verstehen.

 

[Meniskusschaden]

Wie hier jedoch der Fall, wird es ab der Zahl 5 sehr unübersichtlich

Bei 5 geht es noch ganz gut, aber darüber hinaus würde ich auch langsam die Lust verlieren. Um das Prinzip zu verinnerlichen, finde ich es aber trotzdem sinnvoll, es mal aufzuschreiben.

Für eine Visualisierung der Rekursion könnte man das Programm noch leicht abwandeln. Folgendes Programm:

public class Fibonacci {

    public static void main(String[] args) {
        doit(5, 0);
    }

    private static long doit(long n, int level) {
        print("doit("+ n + ")", level);
        long result = n<2 ? n : doit(n-1, level+1) + doit(n-2, level+1);
        print("return "+ result, level);
        return result;
    }
    
    public static void print(String text, int level) {
        for (int i=0; i<level; i++) {
            System.out.print('.');
        }
        System.out.println(text);
    }

}

liefert diese Ausgabe:

doit(5)
.doit(4)
..doit(3)
...doit(2)
....doit(1)
....return 1
....doit(0)
....return 0
...return 1
...doit(1)
...return 1
..return 2
..doit(2)
...doit(1)
...return 1
...doit(0)
...return 0
..return 1
.return 3
.doit(3)
..doit(2)
...doit(1)
...return 1
...doit(0)
...return 0
..return 1
..doit(1)
..return 1
.return 2
return 5