Frage zur Rekursion bei Funktionen

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.

hustbaer

TGGC schrieb:

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.

Was ist daran so schwer nachzuvollziehen? Zeig mir ein Beispiel für Rekursion das mit weniger Code auskommt als eine rekursive Implementierung der Fakultät.

Davon abgesehen halte ich die rekursive Definition der Fakultät sicher nicht für unnötig kompliziert. Ich würde eher sagen dass es die einfachste und eleganteste Art ist die Funktion zu definieren.

SeppJ

hustbaer schrieb:

TGGC schrieb:

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.

Was ist daran so schwer nachzuvollziehen? Zeig mir ein Beispiel für Rekursion das mit weniger Code auskommt als eine rekursive Implementierung der Fakultät.

Das war nicht gesagt. Es ist ein Beispiel gesucht, bei dem die rekursive Definition einfacher ist als die Alternative. Das bedeutet nicht unbedingt, dass die Definition an sich einfach ist, auch wenn dies ein großer Vorteil wäre. Geeignet ist praktisch alles, bei dem man zwei oder mehr Verzweigungen hat. Das ist, wo Rekursion glänzt. Bei nur einem einzelnen Selbstaufruf ist Rekursion eine umständliche Art und Weise, eine Schleife auszudrücken. Das mag in funktionalen Programmiersprachen funktionieren, aber in anderen Sprachen ist der Lernende bereits mit Schleifen vertraut und fragt sich, was der Quatsch soll.

Davon abgesehen halte ich die rekursive Definition der Fakultät sicher nicht für unnötig kompliziert. Ich würde eher sagen dass es die einfachste und eleganteste Art ist die Funktion zu definieren.

$x! = \prod_{i=1}^x i$ lernt jedes Kind so in der Mittelstufe oder davor. Natürlich ohne das $\prod$ . Daher eher "Die Fakultät von x ist das Produkt aller Zahlen von 1 bis x". So wird dir jeder Mensch auf der Straße die Fakultät definieren (sofern sie die Fakultät überhaupt wissen). In welcher Welt wird die Fakultät rekursiv definiert? Die rekursive Definition mag ich hier nicht einmal bringen, weil mir das zu umständlich zu LaTeXen ist.

volkard

SeppJ schrieb:

$x! = \prod_{i=1}^x i$ lernt jedes Kind so in der Mittelstufe oder davor. Natürlich ohne das $\prod$ .

Nee, der nette Lehrer definiert die Fakultät so, aber im Mathebuch steht sie rekursiv definiert.

TGGC

hustbaer schrieb:

Was ist daran so schwer nachzuvollziehen? Zeig mir ein Beispiel für Rekursion das mit weniger Code auskommt als eine rekursive Implementierung der Fakultät.

Ein eleganteres Beispiel in Pseudocode waere fuer mich Folgendes:

CountFilesInDir(name)
{
    ret = 0
    for( f : GetFilesInDir(name))
    {
         if(IsFile(f))
         {
             ret++
         }
         if(IsDirectory(f))
         {
             ret+= CountFilesInDir(name)
         }
    }

    return ret
}

Warum ist das jetzt besser zum lernen?
a) Die Funktion mach schon was sinnvolles ohne den rekursiven IsDirectory Teil
b) Verzeichnisstrukturen sind vielen bekannt, darum faellt es leichter darin zu denken
c) andere Implemtierungen sind weniger elegant, weil hier sinvolle Daten auf dem Stack liegen
d) Laesst sich (als Uebungsaufgabe) auch simpel auf z.b. Groesse aller Dateien oder Ausgabe eines Verzeichnisbaumes umbauen

volkard schrieb:

Nee, der nette Lehrer definiert die Fakultät so, aber im Mathebuch steht sie rekursiv definiert.

Nein.

hustbaer

@SeppJ

TGGC schrieb:

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

hustbaer schrieb:

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.

SeppJ schrieb:

Das war nicht gesagt. Es ist ein Beispiel gesucht, bei dem die rekursive Definition einfacher ist als die Alternative.(...)

WTF?

Columbo

@minastaros: Ja, ich sehe ein, dass ich wohl Unrecht hatte. Sorry.

hustbaer

@TGGC
Ja, ist ein schönes Beispiel.

Vorteile: realistisch, rekusriv viel einfacher als nicht-rekursiv.

Nachteile: in Standard C++ nicht schreibbar (weil es keine Standardfunktionen gibt um Verzeichnisse aufzulisten). Und: hier wird Rekursion auf eine rekursive Datenstruktur angewandt. Was mir dabei fehlt ist zu zeigen dass man auch viele Problemstellungen die nicht per-se rekursiver Natur sind mittels Rekursion elegant und einfach lösen kann. z.B. Sortieren. Dummerweise ist aber ein einfacher Quicksort oder Mergesort immer noch deutlich mehr Code als die Fakultät oder dein Beispiel. Und vor allem schwerer nachzuvollziehender Code.

TGGC

Fuer mich ist eben die Fakultaet als Rekursion auch ein vergleichweise schwer nachvollziehbarer Code. Darum gibts ja ueberhaupt nur diesen Thread.

minastaros

OK, der Versuch einer Zusammenfassung:

1. Rekursion ist ein wichtiges Konzept und sollte grundsätzlich verstanden werden! (Das geht an M1MSR! Verstehst Du Deinen Code jetzt besser?)

2. Fakultät ist zunächst das Produkt über eine Folge von Zahlen, lässt sich aber auch rekursiv darstellen:
$n!=\begin{cases} 1 &,& n=0 \\ n \cdot (n-1)! &,& n>0 \end{cases}$
(wie im übrigen recht viele ähnlichen Summen oder Produkte, z.B. $1+2+3+4 ... n$ )

3. Die sind zwar zahlentechnisch gut nachvollziehbar, aber recht sinnlos in der Programmieranwendung, weil sie genauso gut oder besser iterativ lösbar sind (Ausnahmen vielleicht in Lisp oder Scheme, die z.T. keine Schleifen haben).

4. Es gibt Anwendungsfälle, die von der praktischen Seite her besser greifbar sind und wo Rekursion perfekt und elegant ist.

PS: 5. Der eine versteht die knappen, nackten Zahlen besser, der andere die praktischen Dinge wie Verzeichnisse. Beides denke ich gut, wenn es dem Verständnis hilft.

nachtfeuer

Man versteht es, glaube ich, noch etwas besser, wenn man das Programm mit Standardloops umsetzt (while, for, goto o.ä)
Rekursion ist hier eine Technik, die das Rückwärtszählen a la

1 print x
2 x = x -1
3 zurück zu 1

ohne expliziten Sprungbefehl (wohin nochmal springen?) erlaubt.

volkard

TGGC schrieb:

Ein eleganteres Beispiel in Pseudocode waere fuer mich Folgendes:

CountFilesInDir(name)
{
    ret = 0
    for( f : GetFilesInDir(name))
    {
         if(IsFile(f))
         {
             ret++
         }
         if(IsDirectory(f))
         {
             ret+= CountFilesInDir(name)
         }
    }

    return ret
}

Naja, die andere Variante ist jetzt nicht soo unglaublich unhübsch.

CountFilesInDir(name)
{
    ret = 0
    todo = [name]
    while ( todo )
    {
        name = todo.pop()
        for( f : GetFilesInDir(name))
        {
            if(IsFile(f))
            {
                ret++
            }
            if(IsDirectory(f))
            {
                todo.push(name)
            }
       }
    }

    return ret
}

SeppJ

Und somit ist bewiesen: Rekursion ist vollkommen nutzlos, da sie effektiv bloß eine bequeme Implementierung eines Stacks ist.