Rekursionen verstehen

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.