Rekursionen verstehen

dreaddy

Also irgendwie ist das immer das Gleiche, ich schau mir das fies verrekursivte Programm an und hab nach ner Minute nen Knoten im Hirn und weiss überhaupt nicht wo er nun reinspringt ^^

http://www.infws02.de/attachment.php?attachmentid=1091 Aufgabe 6 auf blatt 3 meiner heldenhaft mittwoch geschriebenen Klausur ist z.B. wieder son Vertreter, ich dreh wennich mir sowas anschau echt durch und verlier total den Faden ^^

Hier nomma die Aufgabe rausgeschrieben:

public class Test
{
public static int x(int a, int b)
{
return b> 0 ? x(a+1, b-1) : a;
}
public static int y(int a, int b)
{
return b>1?x(a,y(a,b-1)) : a;
}
public static int z(int a, int b)
{
return b>0 ? y(a,z(a,b-1)) : 1;
}
public static void main(String[] args)
{
System.out.println(x(6,3));
System.out.println(y(6,3));
System.out.println(z(6,3));
}
}

Gibt es da irgendwie einen Trick oder so wie man die Viecher verstehen kann? :x

Michael E.

Wenn ich ne Rekurstion nicht raff, nehm ich mir immer ein Blatt und rechne ein Beispiel durch. Am effektivsten ist es IMHO, wenn man nur die Funktionsaufrufe hinschreibt (natürlich mit den ausgerechneten Werten).

Codehure

Moin Moin

To understand recursion you first need to understand recursion.

Mal im Ernst zeichne die dir Aufgabe wenn die Rekursion zu schwer wird. Rekusionen sind dafür berüchtigt das sie sehr schnell sehr unübersichtlich werden.
Versuche die Abfolge von Aufrufen darzustellen und übe. Umso mehr die rekusive Funktionen du kennst bzw. durchschaust umso einfacher werden die nächsten. Rekusionen die in jeder Stufe die gleichen Aktionen durchführen (z.B. einen Verzeichnisbaum zu durchsuchen) sind einfacher als solche die bie jedem Aufruf andere Aufgaben übernehmen ( z.B. extreme Verkleinerung von Quellcode in nahezu unwartbare Methoden).

cu CodeHure

Walli

Bei einfachen Rekursionen stelle ich mir den Ablauf im Kopf dar, bei schwierigen zeichne ich einen Graphen oder rechne ein kurzes Beispiel durch. Solche Sachen wie du in deiner Klausur hattest haben mich auch in meiner Progra-Klausur genervt. Ist reine Schikane, ähnlich wie dumme Einheiten bei Physikaufgaben.

Power Off

Der einfachste Weg, Rekursionen zu verstehen, ist z.B. printf-Anweisungen in den Code reinzubauen, also in diesem Fall, z.B.:

Hier mal eine C++ Version, da ich kein C# kann:

#include <iostream>

using namespace std;

class Test {
   public:
   static int x( int a, int b ) {
      cout << "x() aufgerufen mit: a = " << a << ", b = " << b << endl;
      return b > 0 ? x(a+1, b-1) : a;
   }
   static int y( int a, int b ) {
      cout << "y() aufgerufen mit: a = " << a << ", b = " << b << endl;
      return b>1?x(a,y(a,b-1)) : a;
   }
   static int z( int a, int b ) {
      cout << "z() aufgerufen mit: a = " << a << ", b = " << b << endl;
      return b>0 ? y(a,z(a,b-1)) : 1;
   }
   static void main( void ) {
      cout << "Ergebnis von x(6,3) = " << x(6,3) << endl;
      cout << "Ergebnis von y(6,3) = " << y(6,3) << endl;
      cout << "Ergebnis von z(6,3) = " << z(6,3) << endl;
   }
};

int main( int argc, char** argv ) {
   Test::main();
   return 0;
}

net 0

sind das nicht alles sogenannte 'endrekursive funktionen'? die kann man auch alle als schleife coden d.h. dann ohne selbstaufrufe

Taurin

net schrieb:

die kann man auch alle als schleife coden d.h. dann ohne selbstaufrufe

Man kann *alle* Rekursionen als Iterationen beschreiben. Rekursionen sind häufig nur einfacherer.

DrZoidberg

dreaddy schrieb:

public class Test
{
public static int x(int a, int b)
{
return b> 0 ? x(a+1, b-1) : a;
}
public static int y(int a, int b)
{
return b>1?x(a,y(a,b-1)) : a;
}
public static int z(int a, int b)
{
return b>0 ? y(a,z(a,b-1)) : 1;
}
public static void main(String[] args)
{
System.out.println(x(6,3));
System.out.println(y(6,3));
System.out.println(z(6,3));
}
}

Die Funktion x ist die einzige, die nur sich selbst aufruft und keine der anderen Funktiónen. Daher sollte man sich die natürlich zuerst ansehen.
Wenn der aufruf z.B. so lautet: x(3,4), dann sieht die Sache ungefähr so aus:
x(3,4)
x(4,3)
x(5,2)
x(6,1)
x(7,0)
Dann ist b=0 und damit wird die Funktion 7 zurückliefern.

Die Funktion x addiert also einfach nur die beiden Werte a und b.
Gegenbeweis: a+b=(a+1)+(b-1). Für den Fall das b=0 ist a+b=a.

Jetzt kann man die Funktion y entsprechend vereinfachen, da ja jetzt bekannt ist was x macht.

public static int y(int a, int b)
{
return b>1?(a+y(a,b-1)) : a;
}

Diese Funktion addiert a solange auf bis b 0 ist und veringert b jeweils um 1.
Sie multipliziert also a mit b.

Die Funktion z potenziert.

Jester

Die Analyse ist noch nicht ganz korrekt: x addiert nicht immer. Ist b nämlich kleiner 0, so wird einfach a zurückgegeben.

Codehure

Taurin schrieb:

Man kann *alle* Rekursionen als Iterationen beschreiben. Rekursionen sind häufig nur einfacherer.

Moin Moin

Einfacher? Meistens werden Sie nur kürzer aber nicht einfacher, eher komplizierter bzw. universeller. Da die festen Grenzen die sich bei der iterativen Programmierung ergeben durchbrochen werden. Rekusuionen sind imho leichter zu skalieren und universeller als iterative Abläufe.

Anstatt den printf Anweisungen würde ich den Debugger empfehlen, so kann man den Ablauf verfolgen und so in den Code einsteigen und kann sich auch Variablen anzeigen die in der Vorüberlegung vergessen worden sind. Durch die Benutzung des Debuggers stellt sich imho auch die Funktionsweise einer Rekusion besser da. Aber jeder hat seine Methode und die EierlegendeWollMilchSau die jeden Code zufriedenstellt gibt es leider nicht.

cu CodeHure

Helium

Ist reine Schikane, ähnlich wie dumme Einheiten bei Physikaufgaben

Das meinst du nicht ernst. Einheiten sind doch die einfachste und schnellste Form der Probe. Wenn die Einheiten nach einer Umstellung nicht mehr passen, weißt du sofort, dass du einen Fehler hast.

Codehure schrieb:

Taurin schrieb:

Man kann *alle* Rekursionen als Iterationen beschreiben. Rekursionen sind häufig nur einfacherer.

Moin Moin

Einfacher? Meistens werden Sie nur kürzer aber nicht einfacher, eher komplizierter bzw. universeller. Da die festen Grenzen die sich bei der iterativen Programmierung ergeben durchbrochen werden. Rekusuionen sind imho leichter zu skalieren und universeller als iterative Abläufe.

Inwiefern leichter zu skalieren?

Walli

Helium schrieb:

Ist reine Schikane, ähnlich wie dumme Einheiten bei Physikaufgaben

Das meinst du nicht ernst. Einheiten sind doch die einfachste und schnellste Form der Probe. Wenn die Einheiten nach einer Umstellung nicht mehr passen, weißt du sofort, dass du einen Fehler hast.

Falsch verstanden! Ich meinte mit "dumme Einheiten" ungebräuchliche, also z.B. kN/mm^2 oder dm/s. Das nervt einfach gewaltig und kostet nur unnötig Zeit, wenn man mit den Zehnerpotenzen rumzuspielen muss, also reine Schikane.