Rekursion

Hallo,

Ich bin gerade in meinem Buch (C/C++ Das umfassende Lehrbuch) beim Kapitel funktionen. Darunter das Thema Rekursion das ich nicht ganz verstehe.

Beispiel:

long fak_rekursiv(int n)
    {
    if(n == 1)
         return 1;
    return n * fak_rekursiv(n - 1);
    }

Was passiert wenn die Funktion mit n multipliziert wird? (ich kann mir das schwer vorstellen :()
Wie sieht es aus wenn eine Funktion zurückgegeben wird?

MfG
Der Hans

hallo,
es wird nicht die funktion multipliziert und auch nicht zurückgegeben. in beiden fällen ist es der rückgabewert der funktion.

mfg,
m.

_matze

Die Funktion ruft sich einfach selbst auf, das ist der Kern der Rekursion. Und es wird halt direkt mit dem Rückgabewert der Funktion gerechnet. Geh den Ablauf einfach mal schrittweise mit dem Debugger durch, dann wird dir vermutlich einiges klar.

dercooleauswandere

Hallo.
Also Rekursion ist wirklich nicht so einfach zu verstehen . Im Prinzip macht eine Funktion irgend etwas und gibt dann einen Wert zurück. So und hier ist der Unterschied das sich die Funktion immer seklbst aufruft, es sei denn der übergebene wert ist 1. Das PRoblem bei der Rekursion ist, das viel mehr daten im speicher gehalten werden müssen . Rücksprungadresse... somit kann es vorkommen , dass eine rekursive funktion irgendwan einen speicherüberlauf hervorruft. das bedeutet der sopeicher ist einfach voll mit daten, dann ist es hilfreich das ergebnis ietrativ zu berechnen. in vielen fällen geht das auch aber nicht in allen !
ich hoffe die antowrt hat dir ein bisschen weiter geholfen und dein verständnis getärkt wenn nicht frage einfach noch mal

_matze

dercooleauswandere schrieb:

Hallo.
Also Rekursion ist wirklich nicht so einfach zu verstehen . Im Prinzip macht eine Funktion irgend etwas und gibt dann einen Wert zurück. So und hier ist der Unterschied das sich die Funktion immer seklbst aufruft, es sei denn der übergebene wert ist 1. Das PRoblem bei der Rekursion ist, das viel mehr daten im speicher gehalten werden müssen . Rücksprungadresse... somit kann es vorkommen , dass eine rekursive funktion irgendwan einen speicherüberlauf hervorruft. das bedeutet der sopeicher ist einfach voll mit daten, dann ist es hilfreich das ergebnis ietrativ zu berechnen. in vielen fällen geht das auch aber nicht in allen !
ich hoffe die antowrt hat dir ein bisschen weiter geholfen und dein verständnis getärkt wenn nicht frage einfach noch mal

Kleine Ergänzung: Es ist nicht der Hauptspeicher, der irgendwann voll ist (hast du auch nicht gesagt, könnte er aber vielleicht vermuten), sondern der Stack. Auch wenn du den Stack in der Größe durch den Compiler anpassen kannst, einen unendlichen Stack gibt es nicht, und somit sollte man sich bei Rekursionen, wenn möglich, sicher sein, dass die Rekursionstiefe nicht alle Dimensionen sprengt.

Ausprobieren kannst du das bei Interesse ja mal mit einem kleinen Testprogramm mit garantiertem Überlauf:

void rek() {
	static int countRek=0;
	countRek++;
	std::cout << countRek << std::endl;
	rek();
}

int main() 
{
	rek();
}

Kurze Frage zu diesem Thema von mir. Ich habe eine Funktion wie die im ersten beitrag nur ohne die letzte Zeile in der Klammer. Der Compiler meckert auch nicht wenn ich kompiliere. Er gibt aber eine Warnung das in der Funktion nicht alles einen Rückgabewert zurückgibt.

SG1

Und wo ist jetzt Deine Frage?

_matze

btbtbt schrieb:

Kurze Frage zu diesem Thema von mir. Ich habe eine Funktion wie die im ersten beitrag nur ohne die letzte Zeile in der Klammer. Der Compiler meckert auch nicht wenn ich kompiliere. Er gibt aber eine Warnung das in der Funktion nicht alles einen Rückgabewert zurückgibt.

Wenn du die letzte Zeile nicht drin hast, was macht die Funktion dann?? Die gibt 1 zurück bei n==1, ansonsten macht sie gar nix?

Jedenfalls beschwert sich der Compiler zurecht. Nicht jeder Pfad gibt einen Wert zurück. Wenn n!=1, dann wird eben nix zurückgegeben. Das ist blöd, wenn doch aber irgendwo ein Wert erwartet wird...

_matze schrieb:

.... dann wird eben nix zurückgegeben. Das ist blöd, wenn doch aber irgendwo ein Wert erwartet wird...

Das ist aber nicht der Fall. Es wird immer etwas zurückgegeben, auch wenn die Bedingung nicht zutrifft.
Mein Compiler würde in diesem Fall einfach das n zurückgeben.

_matze

zurückgeber schrieb:

_matze schrieb:

.... dann wird eben nix zurückgegeben. Das ist blöd, wenn doch aber irgendwo ein Wert erwartet wird...

Das ist aber nicht der Fall. Es wird immer etwas zurückgegeben, auch wenn die Bedingung nicht zutrifft.
Mein Compiler würde in diesem Fall einfach das n zurückgeben.

Es ist aber nicht definiert, was dann zurückgegeben wird... Sowas sollte man vermeiden, stimmst du mir da zu?

Bashar

Rekursion ist eigentlich ganz einfach zu verstehen. Der OP hat hier aber offenbar noch nichtmal Funktionen verstanden. Erstmal laufen lernen, dann rennen!

zurückgeber schrieb:

Das ist aber nicht der Fall. Es wird immer etwas zurückgegeben, auch wenn die Bedingung nicht zutrifft.
Mein Compiler würde in diesem Fall einfach das n zurückgeben.

Weil das n wohl gerade zufällig in dem Register liegt, dass auch für den Rückgabewert verwendet wird. Das kann ganz schnell schief gehen.

_matze schrieb:

Es ist aber nicht definiert, was dann zurückgegeben wird... Sowas sollte man vermeiden, stimmst du mir da zu?

jepp, so ist es.
(jepp==ja)

_matze

switch(enumAnswer) {
case Ja:
case Jepp:
	std::cout << "Alles klar!";
	break;
}

_matze schrieb:

std::cout "Alles klar!";

da fehlt der links-shift.

_matze

+fricky schrieb:

_matze schrieb:

std::cout "Alles klar!";

da fehlt der links-shift.

Klugsch...

Bashar ich hab die Funktionen schon vertstanden.

Was jedoch nicht ganz in meinen Kopf reingeht ist, wie sich die Funktion selber aufruft und gleichzeitig ein Rückgabewert sein kann.

Thx für die bisherigen Antworten.

_matze

Der Hans schrieb:

Bashar ich hab die Funktionen schon vertstanden.

Was jedoch nicht ganz in meinen Kopf reingeht ist, wie sich die Funktion selber aufruft und gleichzeitig ein Rückgabewert sein kann.

Das ist schon ein kleiner Widerspruch, aber na ja...

Deine Funktion hat einen Rückgabewert. D.h., immer wenn sie aufgerufen wird, gibt sie auch einen Wert zurück. Wenn sie sich nun selbst wieder aufruft (was bedeutet, dass da eine zweite Funktion selben Typs, eine Kopie der Funktion mit eigenen Variablen, läuft, wenn man so will), dann ändert das nichts daran, dass eine Rückgabe stattfindet. Auch wenn der Rückgabe-Wert in der "ersten" Funktion verarbeitet wird. Klar? Oder zumindest klarer?

Jo klarer
Betrachten wir mal die folgende Zeile (bei n = 3):

return n * fak_rekursiv(n - 1);

Statt fak_rekursiv(n - 1) schreiben wir mal fak_rekursiv(2).
Das 3 - 1 = 2 ist, ist mir klar. Aber wieso bekommt die Funktion den Wert 2 damit man mit dem rechnen kann..?

_matze

Na du willst ja erreichen, dass bei Fakultaet(5) 5*4*3*2*1 gerechnet wird. Also rufst du beim ersten Mal n*Fakultaet(n-1) auf, also 5*Fakultaet(4). Fakultaet(4) ist 4*Fakultaet(3) usw. Am besten du schreibst dir mal Schritt für Schritt jeden Aufruf und das Ergebnis auf ein Blatt Papier, dann sollte es klar sein.

Bashar

Der Hans schrieb:

Bashar ich hab die Funktionen schon vertstanden.

Was jedoch nicht ganz in meinen Kopf reingeht ist, wie sich die Funktion selber aufruft und gleichzeitig ein Rückgabewert sein kann.

Würdest du die fak_rekursiv-Funktion verstehen, wenn da statt fak_rekursiv ein Aufruf einer anderen Funktion (z.B. fak_iterativ) stehen würde? Was du geschrieben hast, liest sich eher so, als hättest du mit dem grundsätzlichen Konzept von Funktionen und Rückgabewerten Probleme.