Rekursion - Ich raffs nicht

[DerLernende]

Hallo zusammen!
Ich habe mich hier angemeldet, da ich einfach nicht mehr weiterkomme und hoffe, hier kann mir jemand das Thema endlich in den Kopf hämmern. =D

Es geht um Rekursion. Die gängigen Beispiele dazu sind ja immer die Fakultät und die Fibonacci-Zahlen.
Die beiden kann ich auch ganz gut nachvollziehen (kann man sich ja auch schön als Baum der Methodenaufrufe aufmalen). Aber mit allem anderen tue ich mich irgendwie schwer und leider gehen alle Übungen (die ich zumindest bisher gefunden habe) nie über die beiden Funktionen hinaus (oder schießen so an meinem Horizont vorbei, dass ich lieber noch wegschaue (TowersOfHanoi z.B)). In unserem Lehrbuch tauchen allerdings auch andere Aufgaben auf, die ich gern verstehen würde.

z.B.

    static int p(int x) {
        if(x==0) return 1;
        else {
            int y = p(x-1);
            System.out.println(x+y);
            return y+1;
        }
    }

Irgendwie kann ich mir die Lösung bzw. den Algorithmus der Aufgabe einfach nicht so richtig vorstellen (auch der Debugger half da nicht so richtig).

In y geschieht also der rekurisve Aufruf bis p(0). Der gibt dann 1 an y zurück.
x ist nun ja auch 1 also wird geprinted 1+1 (2). Soweit so gut. Nur ab jetzt windets sich bei mir im Hirn irgendwie...
Jetzt wird ja return y+1 ausgeführt.. Wieso weshalb warum wohin wird nun y+1 returned? Usw....

Könnte mir das jemand erklären/aufmalen?

Hoffe mir kann jemand weiterhelfen!
Gruß

 

[httpdigest]

Also, wenn du die rekursive Fibonacci Funktion schon verstanden hast, dann ist das hier doch um _einiges_ einfacher, oder?
Ist ja nur linear-rekursiv. Da ist Fibonacci schon um einen Zacken schärfer/härter. Aber okay.

Wieso weshalb warum wohin wird nun y+1 returned?

Naja, durch `return y+1;` erhält nun der Aufrufer von `p(x-1)` eben genau dieses Ergebnis - also der Aufruf, der zu der Ausführung der Methode `p` führt, in der wir gerade sind und in der wir genau das `return y+1;` ausführen.

 

[DerLernende]

Glaub ich muss mir das immer irgendwie "visualisieren" können ums nachzuvollziehen. Das geht mit Fibonacci und Fakultät prima, da kann man sich alles schön aufmalen und sieht sofort was Sache ist.

Hier bin ich nur zu doof mir das irgendwie "aufzumalen" o.ä. Aber trotzdem schonmal danke für deine Antwort! Ich versuch das nochmal zu verstehen. Gerne aber noch weitere Hilfestellungen!

 

[DerLernende]

Okaay, glaub ich habs jetzt.
Aber so richtig sicher fühl ich mich in dem Thema immer noch nicht.

Kennt hier vielleicht jemand ein paar Übungen? Also wieder nach dem Schema: Gegebener Code und man soll die Ausgabe(n) hinschreiben?
Unser Übungsbuch hat leider nur 2 Aufgaben dieser Sorte. Eine war easy und dann noch die hier, die nun auch abgehakt ist.

 

[jari]

Türme von Hanoi (rekursiv oder iterativ) sind eher eine mathematische Spielerei als etwas Nützliches im Alltag...

Was verstehst du an dem gezeigten Beispiel nicht? Der Parameter wird jedes mal um 1 verringert, also nix Aufregendes...

 

[DerLernende]

Wie gesagt: Glaub die kann ich nun auch auch abhaken. Würde nur nun noch gerne weitere Aufgaben der Art haben um "sicher" in dem Gebiet zu werden. Hab zwischenzeitlich noch 2 gefunden:

    static int power(int num, int exp) {
        if (exp == 0) {
            return 1;
        }
        if (exp == 1) {
            return num;
        }
        return num * power(num, exp - 1);
    }

    static int sum(int n) {
        if (n > 0) {
            return n + sum(n - 1);
        } else {
            return n;
        }
    }

Nur die sind wieder zu einfach... Gibts denn nix zwischen sum und TowersOfHanoi vom Schwierigkeitsgrad?

 

[jari]

Ackermann schon angeschaut? (NEIN, Spaß )

 

[DerLernende]

 function ack(n, m)
     if n = 0
         return m + 1
     else if m = 0
         return ack(n - 1, 1)
     else
         return ack(n - 1, ack(n, m - 1))

Okay die sieht schon bissl "ekliger" aus... Kommt trotzdem auf die Liste an Funktionen die ich mir morgen mal ansehen werde.
Brauch einfach Übung, Übung, Übung in dem Ganzen um mich da einigermaßen wohl zu fühlen.. ^^ Also gerne meeeehr

 

[Mart]

türme von hanoi, bäume tiefensuche und breitensuche, binär suche sind klassiker für rekursion

 

[DerLernende]

Danke! Schau ich mir morgen alles an. Glaub heut hat sich der größte Knoten bereits gelöst was das Ganze angeht.

 

[Mart]

fang nicht mit hanoi an ...

 

[jari]

Hier sind auch viele Beispiele:

Javabeginners - Rekursion

javabeginners.de

Weitere Rekursionsbeispiele
Bubblesort
Mergesort
Quicksort
Binäre Suche
Interpolationssuche
Dateibaum durchlaufen
Dateien umbenennen
Verzeichnisinhalt packen
Dateigröße ermitteln
Einfach verkettete Liste

 

[DerLernende]

@jari genau sowas hab ich gesucht. Perfekt!

Dann nochmal vielen Dank an alle! Hoff ich bin nu nicht zu euphorisch weil ich die paar pille-palle Aufgaben verstanden hab und morgen dann wieder so darsitze:

 

[Mart]

https://9gag.com/gag/aQX4mbW um türme von hanoi bildlich darzustellen

 

[Hansen_07]

@DerLernende

Hier kannst du dich zum Thema Üben von Rekursion ebenfalls gut austoben.

 

[DerLernende]

https://9gag.com/gag/aQX4mbW um türme von hanoi bildlich darzustellen

Einerseits beruhigend zu wissen, dass ich nicht der einzige bin, den das abschreckt..
Mathematik + Informatik scheint mir ohnehin eine sehr gefährliche Mischung zu ergeben... (ja, eig ist's ja alles mehr oder weniger Mathe aber ihr wisst scho... )

 

[Mart]

du hast halt IT mathematik