Frage zu Rekursion... [Archiv]

Gast

2006-07-08, 18:56:22

Hallo !

Irgendwie bin ich zu dämlich, dieses kleine Programm zu verstehn:

#include <iostream>
using namespace std;

void down(int n)
{
cout << n << endl;

if(n>1)
{
down(n-1);
cout << n << endl;
}
}

void main()
{
down(10);
system("PAUSE");
}

Dass am Anfang von 10-1 runtergezählt wird ist mir klar, aber wieso zum Teufel wird anschließend wieder bis 10 hochgezählt ?! Ich habe dringend Erklärungsbedarf und bin für jede sinnvolle Hilfe dankbar...

Marscel

2006-07-08, 19:04:30

Weil erst die rekursiven Funktionsaufrufe getätigt werden und dann in die andere Richtung die Funktionen wieder verlassen werden, sodass der dort übergebene Wert ausgegeben wird, nicht der um ein verkleinerte.

Ist ja praktisch so:

10
9
8
...
8
9
10

Gast

2006-07-08, 19:07:58

Kapier ich jetzt irgendwie nicht, geht das auch anschaulicher ? :)

Spearhead

2006-07-08, 19:27:39

Immer dort wo der Aufruf von "down" passiert, wird der aktuelle Aufruf unterbrochen.
D.h. er arbeitet erst

void down(int n)
{
cout << n << endl;

if(n>1)
{
down(n-1);

ab, startet dann an dem Punkt wieder von oben.

als Beispiel mit n = 2:

Aufruf down(2)

cout << n << endl;

if(n>1)
{
down(n-1);

- Unterbrechung -

Aufruf von down(1)

cout << n << endl;

if(n>1) -- hier ist n = 1, daher kein weiterer down-Aufruf
{
down(n-1);
cout << n << endl;
}

- Fortsetzung von down 2 -

cout << n << endl;
}
}

-- Ende von down(2) --

Hat das bissle geholfen?

Gast

2006-07-08, 19:37:51

Danke für eure Mühe !

Soweit ich das verstanden habe, erklärt das jetzt auch nur, wie von der übergebenen Zahl runtergezählt wird. Wie er ab 1 wieder bis zur ursprünglich übergebenen Zahl hochzählt, wird mir daraus leider nicht ersichtlich.

UliBär

2006-07-08, 19:40:20

void down(int n)
{
cout << n << endl; // <- Erste Ausgabe

if(n>1)
{
down(n-1); // <- Rekursion
cout << n << endl; // <- Zweite (!!) Ausgabe
}
}

Erst wird die aktuelle Stufe ausgegeben.
Dann folgt die Rekursion.
Dann wird nach zurückkommen nochmal die aktuelle Stufe ausgegeben.

Coda

2006-07-08, 19:40:42

Die Funktion gibt doch zwei mal ne Zahl aus. Einmal vor und einmal nach der Rekursion. Deshalb zuerst runter und dann hoch.

Gast

2006-07-08, 19:42:40

Zusatz:

Wenn ich bei 1 angekommen bin, wird der Ausdruck n>1 ja falsch, d.h. er kommt anschließend nicht mehr in die Schleife rein. Wie das mit dem hochzählen dann funktionieren soll, will mir einfach nicht in den Kopf gehn.

Ich hab jetzt mal nen Haltepunkt gesetzt und da ist mir aufgefallen, dass wenn ich im Visual C auf "weiter" drücke, immer die nächste Zahl Schritt für Schritt bis zur "2" angezeigt wird, was soweit auch logisch ist. Beim nächsten "weiter" werden die 1 plus die Zahlen von 2-10 auf einmal angezeigt.

Gast

2006-07-08, 19:55:26

Also die Erklärung von Spearhead mit 2 als Ursprungswert, dem Abbruch und der Fortsetzung ist mir jetzt klar geworden ! Bei einem Ursprungswert >2 hapert es aber wieder...
Wie wird da hochgezählt, wenn ich nicht mehr in die Schleife komm ? Ich weiß, dass ihr im Prinzip schon alles gesagt habt, aber für einen Anfänger wie mich ist das halt leider nicht sofort ersichtlich.

Spearhead

2006-07-08, 20:01:20

also bei down(3) kommt er in die Schleife, gibt 3 aus, fängt mit down(2) an, gibt 2 aus, fängt mit down(1) an, gibt 1 aus, die if-Abfrage ruft down nicht mehr auf, down(1) gibt danach ja nochmal 1 aus.
Danach geht down(2) weiter, was ja an dem Punkt vom Aufruf von down(1) unterbrochen wurde.
Dort ist n ja wieder 2, also wird 2 ausgegeben.
Danach ist down(2) fertig und down(3) geht weiter, was durch down(2) unterbrochen wurde und gibt 3 aus.

EDIT: Wichtig ist halt, wenn down innerhalb von down aufgerufen wird, bleibt der aktuelle Aufruf an der Stelle stehen, bis der weitere Aufruf fertig ist.

del_4901

2006-07-08, 20:06:41

Gast[/POST]']Also die Erklärung von Spearhead mit 2 als Ursprungswert, dem Abbruch und der Fortsetzung ist mir jetzt klar geworden ! Bei einem Ursprungswert >2 hapert es aber wieder...
Wie wird da hochgezählt, wenn ich nicht mehr in die Schleife komm ? Ich weiß, dass ihr im Prinzip schon alles gesagt habt, aber für einen Anfänger wie mich ist das halt leider nicht sofort ersichtlich.

Er zählt runter weil er nach der Abruchbedingung !(n>1)
9 Stackframes auf dem Stack zu liegen hat, jeder dieser Stackframes wird wieder "abgeräumt" und jeder dieser Stackframes hat eine lokale Variable n. Die nochmal ausgegeben wird.

Du musst das so verstehen, bei jedem Funktionsaufruf wird ein Stackframe erzeugt (mit allen lokalen Variablen) und auf dem Stack abgelegt. Läuft die Funktion zuende, wird der Stackframe wieder abgeräumt.

Sind keine Stackframes mehr im Stack ist die "main" zuende gelaufen und das Programm beendet.

Marscel

2006-07-08, 20:09:26

Angenommen, wir nehmen statt dem Wert 10 nun 3 (das macht das für mich ein wenig kürzer):

Dann läuft das Programm so ab:

- Funktion down(3) - soll heißen down() bekommt den Wert 3 übergeben
- Funktion down(3) gibt einmal den Wert aus => 3
- Da 3 > 1, wird der Wert 3-1 (=2) weitergegeben: down(2)
-- Funktion down(2)
-- Funktion down(2) gibt einmal den Wert aus => 2
-- Da 2 > 1, wird der Wert 2-1 (=1) weitergegeben: down(1)
--- Funktion down(1)
--- Funktion down(1) gibt einmal den Wert aus => 1
--- Da 1 == 1, passiert nichts
--- Funktionsaufruf down(1) ist zu Ende, Rücksprung
-- Funktion down(2) gibt einmal den Wert aus => 2
-- Funktionsaufruf down(2) ist zu Ende, Rücksprung
- Funktion down(3) gibt einmal den Wert aus => 3
- Funktionsaufruf down(3) ist zu Ende, Rücksprung

Es wird im gesamten Skript NICHTS wieder hochgezählt, nachdem die Funktion zu Ende ist (zurückgegeben wird ja nichts...), geht einfach die Funktion davor, die die "darunter" aufgerufen hat, zu Ende und gibt davor noch einmal das Argument aus...

Einfacher kann ichs nicht erklären. ;)

EDIT: Mist, Spearhead hats schon. :(

Gast

2006-07-08, 20:17:16

Spearhead[/POST]']also bei down(3) kommt er in die Schleife, gibt 3 aus, fängt mit down(2) an, gibt 2 aus, fängt mit down(1) an, gibt 1 aus, die if-Abfrage ruft down nicht mehr auf, down(1) gibt danach ja nochmal 1 aus.
Danach geht down(2) weiter, was ja an dem Punkt vom Aufruf von down(1) unterbrochen wurde.
Dort ist n ja wieder 2, also wird 2 ausgegeben.
Danach ist down(2) fertig und down(3) geht weiter, was durch down(2) unterbrochen wurde und gibt 3 aus.

EDIT: Wichtig ist halt, wenn down innerhalb von down aufgerufen wird, bleibt der aktuelle Aufruf an der Stelle stehen, bis der weitere Aufruf fertig ist.

Hmm, so klar war mir das wohl doch nicht.
Also nochmal mit 3 als Beispiel:

1. Schritt:

void down(3)
{
cout bzw. printf gibt 3 aus;
if(3>1); // wahr <- also geht in Schleife
{
down(3-1); // =2 und springt wieder hoch zu void down(2)
cout bzw. printf wird hier noch nicht ausgeführt
}
usw.

Soweit richtig ?

Das geht dann so lange, bis void down(n) "1" übergeben bekommt. Da er bei 1 nicht mehr in die Schleife kommt, wie kann er dann mit dem cout IN der Schleife wieder die "2" ausgeben ? Ich bin wirklich untröstlich :D

del_4901

2006-07-08, 20:19:19

Gast[/POST]']
Das geht dann so lange, bis void down(n) "1" übergeben bekommt. Da er bei 1 nicht mehr in die Schleife kommt, wie kann er dann mit dem cout IN der Schleife wieder die "2" ausgeben ? Ich bin wirklich untröstlich :D

Weil es sich hierbei im ein anderes n handelt. ^^

nach der Abruchbedingung sieht das ganze so aus:

down(2)|down(3)|down(4)|down(5)|down(6)|down(7)|down(8)|down(9)|down(10)|main()|

(ich hab also 9 N's auf dem Stack liegen)
dann wird wieder abgeräumt (von vorn).

Gast

2006-07-08, 20:22:21

Hmm, ich glaub so langsam dämmert es...

Bei uns ham das von 30 Leuten 3 verstanden und die konnten es dem Rest nicht plausibel erklären. Habt ihr euch da am Anfang auch so schwer getan ? :)

del_4901

2006-07-08, 20:25:31

Gast[/POST]']Hmm, ich glaub so langsam dämmert es...

Bei uns ham das von 30 Leuten 3 verstanden und die konnten es dem Rest nicht plausibel erklären. Habt ihr euch da am Anfang auch so schwer getan ? :)

naja, ging so ^^ ist eigendl nicht so schwer. Jeder funktionsaufruf, egal ob rekursion oder nicht landet auf dem Stack mit allen lokalen variablen. kommt es zu einem return(), wird der letzte Stackframe gelöscht, und bei dem vorherigen weitergearbeitet. Auf dem Stack liegt auch noch die Rücksprungadresse, damit die CPU weiß, wo im Code sie unterbrochen wurde, damit sie an der Stelle weiterabeiten kann.

Spearhead

2006-07-08, 21:13:31

hehe ja, sobald man es kapiert hat ist es nicht schwer *gg*

man muß einfach damit klarkommen das im Programm nicht einfach in der Funktion

void down(3)
{
cout bzw. printf gibt 3 aus;
if(3>1); // wahr <- also geht in Schleife
{
down(3-1); <- HIER
cout bzw. printf wird hier noch nicht ausgeführt
}

beim erneuten Aufruf ( "<- HIER" ) nicht einfach wieder hoch gesprungen wird und erneut versucht wird die Funktion abzuarbeiten, sondern quasi der komplette Code der Funktion dort nochmal eingefügt wird.

-- Anfang down(3) --
void down(3)
{
cout << n << endl; // ausgabe "3"

if(n>1) // 3 ist größer 1
{

-- Anfang down(2) --
void down(2)
{
cout << n << endl; // ausgabe "2"

if(n>1) // 2 ist größer 1
{

-- Anfang down(1) --
void down(1)
{
cout << n << endl; // ausgabe "1"

if(n>1)
{
down(n-1); // wird nicht wieder ausgeführt, da n = 1 ist
cout << n << endl;
}
}
-- Ende down(1)

cout << n << endl; // ausgabe "2"
}
}
-- Ende down(2) --

cout << n << endl; // Ausgabe "3"
}
}
-- Ende down(3) --

Monger

2006-07-08, 21:22:37

Um Rekursion zu verstehen, muss man erstmal Rekursion verstanden haben! :D

Man tut sich leichter, wenn man sich den Aufruf-Stack vorstellt.
Wenn du es dir bildlich vorstellen willst, vielleicht hilft dir folgender Versuch weiter:

Mach das ganze auf Basis von Zetteln. Jeder Zettel steht für eine Methode. Jedesmal wenn eine neue Methode aufgerufen wird, schreibst du einen neuen Zettel, und legst ihn auf die alten. Jedesmal wenn eine Methode abgearbeitet ist, vernichtest du diesen Zettel.

Es ist etwas mühsam, aber wenn man dieses System tatsächlich zwei, dreimal in der Realität probiert hat, versteht man es besser.

Es ist sowieso grundsätzlich keine schlechte Idee, theoretische Probleme mal in der Realität nachzuspielen, weil daher kommen sie ja letztendlich auch. Nicht umsonst gehören Skatspiele eigentlich zu jeder Informatikvorlesung.

del_4901

2006-07-08, 21:29:21

Monger[/POST]']Um Rekursion zu verstehen, muss man erstmal Rekursion verstanden haben! :D

Man tut sich leichter, wenn man sich den Aufruf-Stack vorstellt.
Wenn du es dir bildlich vorstellen willst, vielleicht hilft dir folgender Versuch weiter:

Mach das ganze auf Basis von Zetteln. Jeder Zettel steht für eine Methode. Jedesmal wenn eine neue Methode aufgerufen wird, schreibst du einen neuen Zettel, und legst ihn auf die alten. Jedesmal wenn eine Methode abgearbeitet ist, vernichtest du diesen Zettel.

Es ist etwas mühsam, aber wenn man dieses System tatsächlich zwei, dreimal in der Realität probiert hat, versteht man es besser.

Es ist sowieso grundsätzlich keine schlechte Idee, theoretische Probleme mal in der Realität nachzuspielen, weil daher kommen sie ja letztendlich auch. Nicht umsonst gehören Skatspiele eigentlich zu jeder Informatikvorlesung.

Zusätzlich dazu kann man sich noch alle lokalen Variablen aufschreiben, und den Befehl bzw. Stelle im Code, wo man unterbrochen wurde.

Monger

2006-07-08, 21:32:30

AlphaTier[/POST]']Zusätzlich dazu kann man sich noch alle lokalen Variablen aufschreiben, und den Befehl bzw. Stelle im Code, wo man unterbrochen wurde.
Exakt! ;)
Alle Informationen, die eine Methode zu einem bestimmten Zeitpunkt hat (angefangen bei den Aufrufparametern), müssen natürlich auch zur richtigen Zeit auf den Zetteln stehen.

Neomi

2006-07-08, 21:42:34

void down(int n)
{
cout << n << endl;

if(n>1)
{
down(n-1);
cout << n << endl;
}
}

Dein Problem hier ist offenbar, daß du denkst, n würde irgendwo wieder hochgezählt. Das wird es nicht. Wenn n=3 ist, dann wird zwar für den nächsten verschachtelten Aufruf n=2 als Parameter übergeben, n wird aber lokal in der aufrufenden Funktion nicht geändert. Dort ist n nach wie vor 3 und wird auch so ausgegeben, wenn die aufgerufene Funktion fertig abgearbeitet ist.

Zur Vereinfachung mal down(3) aufgeschlüsselt in einzelne Funktionen ohne Rekursion, dafür mit konstanten Werten, das sieht dann so aus:

void down1()
{
cout << 1 << endl;
}

void down2()
{
cout << 2 << endl;

down1();
cout << 2 << endl;
}

void down3()
{
cout << 3 << endl;

down2();
cout << 3 << endl;
}

Alles zusammengefaßt in einer Funktion ergibt das hier:

void down3()
{
cout << 3 << endl;

// Aufruf von down2()
{
cout << 2 << endl;

// Aufruf von down1()
{
cout << 1 << endl;
}
cout << 2 << endl;
}
cout << 3 << endl;
}

TheGamer

2006-07-08, 22:40:32

down wiederholt sich halt solange bis die Bedingung nicht mehr stimmt, die Funktion down wurde aber nie abgeschlossen weil sie ja isch immer neu aufgerufen hat. Wenn die Bedingung mal nicht stimmt wird eben n mal alles nach down(n-1) aufgerufen. Dies war ja vorher durch die Rekursion nciht moeglich, muss aber denoch gemacht werden am Schluss

Gast

2006-07-09, 09:14:10

Doch, es sollte jetzt klar sein, danke euch nochmal !

Ich hab noch ein Beispiel gefunden, in dem es quasi ganz genauso läuft:

void verratnix(char *s)
{
if(*s != '\0')
{
verratnix(s+1);
cout << *s;
}
}

void main()
{
char hallo[]={'H', 'a', 'l', 'l', 'o', '\0'};
verratnix(hallo);
system("PAUSE");
}

Wenn ich den Haltepunkt bei "verratnix(s+1)" in der if-Schleife setze, so kann ich im Debugger sehn, das *s erst auf 'H' zeigt, im nächsten Aufruf auf 'a' usw., der Inhalt der übergebenen Zeichenkette ist also zuerst "Hallo" dann "allo" usw.
Da er printf nicht erreicht, wird im Konsolenfenster auch noch nichts ausgegeben. Erst wenn die abschließende "\0" erreicht wurde bzw. die Bedingung falsch ist, erfolgt die Rückkehr aus den jeweils rekursiven Aufrufen und die Ausgabe über den Aufruf von printf lautet dann -> ollaH

Hab ich das jetzt alles richtig beschrieben ? :)