Frage zur Rekursion bei Funktionen

Hallo, ich bin neu in C++ und verstehe die Rekursion nicht.

Bei einer Funktion wie zum Beispiel:

const int fakultaet(const int n)
{
if ( n == 0 )
return 1;
else
return( n * fakultaet(n - 1) );
}

return (n* fakultaet(n - 1));

Was passiert dort genau ? Wird n*(n-1) gerechnet ?

M1SMR schrieb:

Wird n*(n-1) gerechnet ?

Es wird n*(n-1)! gerechnet.

Bengo

Gibt der Funktion mal die Zahl 5.

Sie gibt dir 5 * f(4) zurück.
f(4) = 4 * f(3)
f(3) = 3 * f(2)
f(2) = 2 * f(1)
f(1) = 1

Die Funktion wird insgesammt 5 mal aufgerufen. Und wenn du die obigen Gleichungen zusammenfasst erhälst du f(5) = 5 *4 *3*2*1 = 5!
Genau das was du wolltest.

TGGC

Ich frag mich warum solche Sachen immer die Standard Beispiele fuer Rekursion sind. Niemand benutzt sowas...

Columbo

TGGC schrieb:

Ich frag mich warum solche Sachen immer die Standard Beispiele fuer Rekursion sind.

Weil die mathematische Funktion, die fakultaet repräsentiert, rekursiver Natur ist und dementsprechend kurz und aussagekräftig rekursiv zu implementieren.

Niemand benutzt sowas...

Der Großteil aller Standardbeispiele ist in der Praxis nicht anzutreffen. Der didaktische Nutzen ist eher ein Kriterium.

minastaros

Arcoth schrieb:

TGGC schrieb:

Ich frag mich warum solche Sachen immer die Standard Beispiele fuer Rekursion sind.

Weil die mathematische Funktion, die fakultaet repräsentiert, rekursiver Natur ist und dementsprechend kurz und aussagekräftig rekursiv zu implementieren.

Nein, Fakultät hat per se gar nichts mit Rekursion zu tun, sondern es ist einfach nur das Produkt einer Reihe von natürlichen Zahlen. Rekursion ist eine Möglichkeit, wie man das umsetzen kann, es geht aber viel einfacher mit einer Schleife - und ist einfacher zu begreifen.

Old Joel Spolsky hat glaub ich mal geschrieben, wenn einer seiner Programmierer Fibonacci oder Fakultät per Rekursion implementieren würde, würde er ihn feuern.

Ich denke, dass man Fakultät immer deshalb als "gutes" Lehrbeispiel verwendet, weil es da um die puren Zahlen geht, was man im Kopf noch gut mit verfolgen kann und dadurch die Rekursion verstehen kann. Die mathematische Formel dazu ist vergleichsweise kurz. Im Vergleich z.B. zum "Türme von Hanoi".

Hier eine zufällig gefundene Diskussion über gute und schlechte Anwendungen von Rekursion: http://discuss.fogcreek.com/joelonsoftware4/default.asp?cmd=show&ixPost=142813

hustbaer

Ich glaube der Grund ist einfach dass die Berechnung der Fakultät SO einfach ist, dass dabei nichts aber auch gar nichts von der Rekursion ablenkt.
Man kann also "Rekursion pur" zeigen.

Bei den meisten anderen Beispielen gibt es - abgesehen vom eigentlichen rekursiven Aufruf - viel Code den man zusätzlich noch verstehen muss. Was das Verstehen des Beispiels vermutlich erschwert.

Allerdings hätte ich mir bei vielen Dingen selbst realistischere Beispiele gewünscht. Vielleicht wäre es besser als erstes das einfach Bilderbuchbeispiel bringen, damit man mal versteht was da eigentlich gemacht wird, aber danach noch ein zweites Beispiel das zeigt wie das gerade erlernte in realen Programmen eingesetzt wird.

inflames2k

hustbaer schrieb:

Allerdings hätte ich mir bei vielen Dingen selbst realistischere Beispiele gewünscht. Vielleicht wäre es besser als erstes das einfach Bilderbuchbeispiel bringen, damit man mal versteht was da eigentlich gemacht wird, aber danach noch ein zweites Beispiel das zeit wie das gerade erlernte in realen Programmen eingesetzt wird.

Gebe ich dir voll und ganz recht. Mit der Ausnahme, dass das allgemeine "Allerwelts" Beispiel wohl nicht existieren wird. Außer man beschränkt sich z.B. auf das Durchlaufen eines Baumes.

TGGC

Arcoth schrieb:

Weil die mathematische Funktion, die fakultaet repräsentiert, rekursiver Natur ist und dementsprechend kurz und aussagekräftig rekursiv zu implementieren.

Aeh nein, ist sie nicht. Die Fakultaet in ein Produkt.

minastaros

inflames2k schrieb:

hustbaer schrieb:

Allerdings hätte ich mir bei vielen Dingen selbst realistischere Beispiele gewünscht. Vielleicht wäre es besser als erstes das einfach Bilderbuchbeispiel bringen, damit man mal versteht was da eigentlich gemacht wird, aber danach noch ein zweites Beispiel das zeit wie das gerade erlernte in realen Programmen eingesetzt wird.

Gebe ich dir voll und ganz recht. Mit der Ausnahme, dass das allgemeine "Allerwelts" Beispiel wohl nicht existieren wird. Außer man beschränkt sich z.B. auf das Durchlaufen eines Baumes.

Hier das Bilderbuchbeispiel: Ich hab vor kurzem in einem UML-Tool ein Script geschrieben, was mir aus einem verschachtelten Objektbaum ("Verzeichnisse" und darunterliegende Elemente ähnlich einem Dateiordner) alle UML-Diagramme als Bilder exportiert.
OK, war JavaScript, aber für Rekursion perfekt.

Das Problem ist, dass die Programmier-Lehrbücher (zumindest die, in denen ich was über Rekursion gelesen habe), immer bei Fakultät/Fibonacci aufhören. Sie sagen nicht, dass das nur ein eher schlechtes Beispiel ist. Neben dem Wissen, wie Rekursion funktioniert, muss mMn vor allem ein Bewusstsein gefördert werden, wann man sie gut einsetzt - und wann nicht.

Ansonsten - als Gedankenkonstrukt finde ich Rekursion extrem elegant und genial. Der Aha-Effekt kam glaube ich, als ich verstanden hatte, dass C das ermöglichte, was mein altes C64-BASIC nicht konnte - zumindes nicht einfach so.

Columbo

TGGC schrieb:

Aeh nein, ist sie nicht.

Ich weiß nicht was du gelesen hast, aber "rekusiver Natur" heißt für mich, dass irgendeine Operation ausgeführt wird, und dann die Operationen für f(n-1) ausgeführt werden. Selbst wenn du eine Schleife schreibst, kommt so etwas wie

while (n > 1) prod *= n--;

Und hier wird zuerst mit $n$ multipliziert, und dann mit $(n-1)!$ . Das nenne ich "rekursiver Natur".

Die Fakultaet in ein Produkt.

Danke, ich hatte keine Ahnung.

Old Joel Spolsky hat glaub ich mal geschrieben, wenn einer seiner Programmierer Fibonacci oder Fakultät per Rekursion implementieren würde, würde er ihn feuern.

DIese werden nicht rekursiv implementiert, da sie nicht hübsch endrekursiv implementierbar sind.

minastaros

for( unsigned int k = 1; k <= n; ++k )
    prod *= k;

$n!=1\cdot 2\cdot 3\cdot ...\cdot n=\prod_{k=1}^{n}k$

ist nicht rekursiv.

Wie gesagt, Rekursion ist eine Möglichkeit zur Berechnung, aber nicht deren Natur.

Columbo

minastaros schrieb:

for( unsigned int k = 1; k <= n; ++k )
    prod *= k;
$n!=1\cdot 2\cdot 3\cdot ...\cdot n=\prod_{k=1}^{n}k$

ist nicht rekursiv.

Moment, das kann ich auch
$n!=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 1=\prod_{k=1}^{n}k$

Edit: Vor allem verstehe ich dein Argument nicht. Ich habe genau erklärt was für mich "rekursiver Natur" bedeutet. Und es trifft auf die Fakultät zu. Falls du mit einem von beidem nicht übereinstimmst, musst du schon konkret sagen, was dir nicht passt.

minastaros

Arcoth schrieb:

Moment, das kann ich auch
$n!=n\cdot (n-1)\cdot (n-2)\cdot ...\cdot 1=\prod_{k=1}^{n}k$

Edit: Vor allem verstehe ich dein Argument nicht. Ich habe genau erklärt was für mich "rekursiver Natur" bedeutet. Und es trifft auf die Fakultät zu. Falls du mit einem von beidem nicht übereinstimmst, musst du schon konkret sagen, was dir nicht passt.

Auch das ist nicht rekursiv.
Bei n! = n * (n-1) * (n-2)... führst Du eine Reihe von Multiplikationen eine nach der anderen durch, daher sofort eine Zahl n mit einer weiteren Zahl n-1 und nicht mit (n-1)!

Rekursion bedeutet in meinen Augen, dass ein Wert mit dem Ergebnis des Rests multipliziert wird, der dann auf gleiche Weise erst ermittelt wird.
Also
n! = n * ((n-1) * ((n-2) * ((... 1 ))))))))))

Columbo

Auch das ist nicht rekursiv.

Da hast du recht.

minastaros schrieb:

Rekursion bedeutet in meinen Augen, dass ein Wert mit dem Ergebnis des Rests multipliziert wird, der dann auf gleiche Weise erst ermittelt wird.
Also
n! = n * ((n-1) * ((n-2) * ((... 1 ))))))))))

Auch da stimme ich dir zu.

Ich redete von rekursiver Natur; Vielleicht ist dieser Begriff einfach zu schwammig, und ich benutze ihn viel laxer als du, der es als "nur rekursiv sinnvoll implementierbar" auffasst?

minastaros

Arcoth schrieb:

Ich redete von rekursiver Natur; Vielleicht ist dieser Begriff einfach zu schwammig, und ich benutze ihn viel laxer als du, der es als "nur rekursiv sinnvoll implementierbar" auffasst?

Alles klar.

Dein Beispiel war eine reine Rückwärts-Iteration einer Folge von n auf 1. Von der Implementierung her alles OK und richtig! Es macht oft Sinn, auf 0 oder 1 runterzuzählen als rauf. Aber da waren keine vorgehaltenen Zwischenwerte bzw. kein Sich-selbst-Aufrufen.

"nur rekursiv implementierbar" meine ich nicht. Fakultät kann man mathematisch sehr schön und absolut gleichberechtigt auch rekursiv beschreiben (und als solches implementieren), von daher ist es durchaus sinnvoll.

Was Joel Spolsky meinte ist jedoch, dass die rekursive Umsetzung (also eine funktion factorial() , die sich selbst aufruft) durch die ganzen Zwischenwerte und den Callstack wesentlich unperformanter ist als eine simple Schleife. In der Mathematik ist das egal, da gibt es - anders als im realen Programm - keine Performance.

TGGC

minastaros schrieb:

Der Aha-Effekt kam glaube ich, als ich verstanden hatte, dass C das ermöglichte, was mein altes C64-BASIC nicht konnte - zumindes nicht einfach so.

https://www.c64-wiki.de/index.php/GOSUB

Arcoth schrieb:

Ich weiß nicht was du gelesen hast, aber "rekusiver Natur" heißt für mich, dass irgendeine Operation ausgeführt wird, und dann die Operationen für f(n-1) ausgeführt werden.

Und gerade das ist doch bei einer Fakultaet nicht noetig denn Multiplikation ist kommutativ. Grundsaetzlich lassen sich ja Iterationen und Rekursionen ineinander umformen, damit waere dann quasi alles "rekursiver Natur". Ok, von mir aus - dann ist das aber keine sinnvolle Begruendung mehr, warum gerade dies als Beispiel benutzt wird.

Auch hustbaers Argument kann ich nicht wirklich nachvollziehen, da zumindest ich eine rekursive Implementation der Fakultaet als unnoetig kompliziert ansehe und nicht als besonders simples Beispiel.

minastaros

TGGC schrieb:

minastaros schrieb:

Der Aha-Effekt kam glaube ich, als ich verstanden hatte, dass C das ermöglichte, was mein altes C64-BASIC nicht konnte - zumindes nicht einfach so.

https://www.c64-wiki.de/index.php/GOSUB

Das BASIC-Beispiel dort ist Schwachsinn. Es macht eine ganz normale Iteration von 1 nach n.

10  REM - DAS RAHMENPROGRAMM
100 INPUT "FAKTORIELLENBERECHNUNG: N=";FA
110 GOSUB 1000
120 PRINT " FAKTORIELLE VON ";FA;"=";FR
130 GOTO 100
1000 REM UNTERPROGRAMM FAKT(FA) -> FR - VERWENDET: I
1010 FR=1: I=1           : REM INITIALISIERUNG
1020 IF I>FA THEN RETURN : REM ABBRUCHBEDINGUNG
1030 FR=FR*I             : REM EIN BERECHNUNGSSCHRITT
1040 I=I+1
1050 GOSUB 1020          : REM REKURSION!
1060 RETURN

Kennzeichen von Rekursion ist, dass es den eigenen Funktionsaufruf selbst wieder enthält.
Das ist hier nicht der Fall:

GOSUB 1020 berechnet nicht (n-1)!, sondern 1k* bzw. *(k-1)!k, oder mit den verwendeten Variablen gesprochen
1*I bzw. (I-1)! * I , wobei (I-1)! bereits berechnet ist (in FR).

(PS: auch die Abbruchbedingung stimmt nicht. Bei der mathematischen Rekursionsformel für Fakultät ist das k==1, hier aber k>n)

Um Fakultät rekursiv mit BASIC umzusetzen, müsste man zumindest bei n anfangen, um dann (n-1)! zu berechnen. Dabei braucht jeder weitere Funktionsaufruf streng genommen eine eigene Ergebnisvariable (auch (n-1)! muss sich sein n merken, um dann zuerst (n-2)! zu berechnen, bevor die eigentliche Multiplikation erfolgt), und die Variablen sind in diesem BASIC eben nicht lokal, sondern global. Das ist das, was ich als "Unterschied zu C" meinte.
Klar kann man auch mit einem globalen Register arbeiten, so wie man Rekursion und Iteration ineinander umformen kann.

PS: OK, hatte mich getäuscht mit den lokalen Ergebnisvariablen. Das dürfte der Mathematik wesentlich näher kommen:

100 LET RE% = 0 : REM Result
110 LET N% = 20 : REM n of n!
120 GOSUB 1000;

1000 IF (N%=1 OR N%=0) THEN RE% = 1: RETURN
1010 N%=N%-1
1020 GOSUB 1000          : REM calculates RE = (n-1)!
1030 N%=N%+1
1040 RE%=N%*RE%
1050 RETURN

TGGC

Ich habe nicht den gesamten Artikel auf Fehler ueberprueft, da ich weiss das man GOSUB Rekusrsion umsetzen kann. Aber mal wieder typisch, das mit der Fakultaet ein moeglichst dummes Beispiel dafuer gewaehlt wird.

minastaros

Ja, Du hast schon recht, je nachdem, um was es geht. Gerade das (untere) Fakultät-Beispiel zeigt ja, dass es geht. Schwieriger ist es eben bei Algorithmen, bei denen sich jede Aufrufebene Werte lokal merken muss, da müsste der C64 dann ein Array nehmen zum Zwischenspeichern.

Aber egal, das C64-BASIC ist etwas off-topic... Hätte nicht damit anfangen sollen.