Rekursion verstehen

[BTR20]

Hi,
ich bin gerade beim Thema Rekursion aber so ganz Blicke ich hier noch nicht durch.

public class RekursionFunction {
    static int rekursion(int a) {
        if (a < 1)
            return 1;

        return rekursion(a - 1) * rekursion(a - 2);

    }

    public static void main(String[] args) {
        System.out.println(rekursion(3));
    }
}

Die Abbruchbedingung wäre für die Methode sobald der Wert kleiner als 0 ist. Falls der Wert der übergeben wird größer ist als 1 geht dieser in den Else Zweig.
Als Ausgabe wird immer 1 ausgegeben bei egal welchen Wert nur verstehe ich hier den else Zweig nicht so genau.

Im Internet habe ich für die Rekursion das Beispiel mit der Fakultät angeschaut aber hier sehe ich nicht dahinter.

Wenn ich jetzt den Wert 3 übergebe wird dieser in den Else Zweig springen rek(2)*rek(1).
Nun ab hier brauche ich eine kurze Erklärung wie es weitergeht weil rek beträgt bei dem einen 2 und bei dem anderen 1 wie geht man da weiter vor?






Lg
BTR20

 

[httpdigest]

Wenn ich jetzt den Wert 3 übergebe wird dieser in den Else Zweig springen rek(2)*rek(1). Nun ab hier brauche ich eine kurze Erklärung wie es weitergeht weil rek beträgt bei dem einen 2 und bei dem anderen 1 wie geht man da weiter vor?

Mache einfach mit rek(2) und rek(1) getrennt voneinander weiter. Das ergibt dann einen Baum an rekursiven Aufrufen, den man so visualisieren könnte:

rek(3) = rek(2) * rek(1)
          |        |
          |        \-------------\
          v                      v
         /-------------\        /--------------\
         rek(1) * rek(0)        rek(0) * rek(-1)
          |        |             |        |
          |        \--------\    v        v
          v                 |    1        1
         /--------------\   v
         rek(0) * rek(-1)   1
          |        |
          v        v
          1        1
      = 1 * 1 * 1 * 1 * 1

 

[BTR20]

Mache einfach mit rek(2) und rek(1) getrennt voneinander weiter. Das ergibt dann einen Baum an rekursiven Aufrufen, den man so visualisieren könnte:

rek(3) = rek(2) * rek(1)
          |        |
          |        \-------------\
          v                      v
         /-------------\        /--------------\
         rek(1) * rek(0)        rek(0) * rek(-1)
          |        |             |        |
          |        \--------\    v        v
          v                 |    1        1
         /--------------\   v
         rek(0) * rek(-1)   1
          |        |
          v        v
          1        1
      = 1 * 1 * 1 * 1 * 1

Vielen Dank für die Erklärung. Die Visualisierung hat mir sehr geholfen. Die Ausgabe beträgt immer 1 für jeden Eingabewert weil dann die Methode solange sich selbst aufruft bis der Wert kleiner als <1 ist und im if zweig ergibt sich immer 1 als Wert. Dann muss man nur noch multiplizieren weil der else Zweig das so vorschreibt das die ganzen Rekursionswerte miteinander multipliziert werden.

Das müsste so dann richtig sein?

 

[mihe7]

Das müsste so dann richtig sein?

Das kann man nicht sagen, weil "die ganzen Rekursionswerte" eine äußerst zweideutige Aussage ist. Dein Beispiel, wo immer nur multipliziert wird, ist ggf. auch nicht völlig geeignet. Interessanter wird es, wenn man es ein wenig ändert:

    static int rekursion(int a) {
        if (a < 1)
            return 1;
        if (a % 2 == 0) // falls a eine gerade Zahl ist
            return rekursion(a - 1) + rekursion(a - 2);
        return rekursion(a - 1) * rekursion(a - 2);
    }

 

[ocsme]

Guten Tag,
also mit Rekursion habe ich was das verstehen an geht nicht mehr viele Probleme sondern meine Frage ist eher:
https://www.java-forum.org/thema/rekursion-ordentlich-aufschreiben.183727/

Wie man das ganze Ordentlich und systematisch aufschreibt. httpdigest macht man dort immer einen Baum? Ich komme damit auch gut klar doch das Problem ist das ich sehr unsystematisch vor gehe und der Baum sehr schnell unübersichtlich wird!

Gibt es da ein paar Tipps? Wir sollen bei uns auch immer nur die Werte angeben das macht das ganze wieder leichter also nicht die Rückruf- und Aufrufterme sondern nur die Werte die raus kommen

LG