Frage zur Rekursion bei Funktionen

[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.

[volkard]

SeppJ schrieb:

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

Da wäre ich nicht sicher. Ich fürchte, sogar gelegentlich Rekursion eingesetzt zu haben, wo sie echt viel schneller und einfacher war.
Bei den Türmen von Hanoi finde ich sie echt viel einfacher.
Beim Zählen der Dateien ist die Bearbeitunsreihenfolge egal. Deswegen isses ein Lehrbuchbeispiel, wo Rekursion plem ist (TGGC~JW).

[TGGC]

SeppJ schrieb:

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

Erzaehl doch mal was neues...