Frage zur Rekursion bei Funktionen

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