ubuntuusers.de

Ich hab mal gelernt, dass der Aufruf von Funktionen und Methoden vergleichsweise lange dauert. Weil Rekursionen außerdem vergleichsweise verwirrend sind, stellt sich mir die Frage: Wozu benutzt man sie sinnvoll?

Es gibt Rekursive Funktionen, die das Programmieren wesentlich vereinfachen.

Zum Beispiel die Fakultät einer Zahl:

ulong Fakultaet(ulong wert)
{
 if(wert == 1)
 {
  return 1;
 }else{
  return wert * Fakultaet(wert - 1);
 }
}

Prädestiniert sind auch das Durchsuchen von Verzeichnissen oder das Durchwandern von Bäumen. Also überall da, wo man das Abbruchkriterium in nicht-rekursiver Schreibweise nicht genau formulieren kann.

Sauer2 schrieb:

Ich hab mal gelernt, dass der Aufruf von Funktionen und Methoden vergleichsweise lange dauert.

Kommt auf die Rekursion an. Endrekursive Funktionen sind genauso schnell wie schleifen. (Wenn man einen ordentlichen Interpreter/Compiler hat)

Weil Rekursionen außerdem vergleichsweise verwirrend sind, stellt sich mir die Frage: Wozu benutzt man sie sinnvoll?

Hast du schon mal versucht in rekursive Datenstrukturen mit iterativen Funktionen zu arbeiten? Oder bei rekursiven Problemen wie den Fibonacci-Zahlen. Da sind die rekursiven Funktionen sehr viel leichter zu verstehen.

Klar prinzipiell sind Rekursionen erstmal nicht sehr performant. Es gibt aber Sprachimplementationen, die beispielsweise tail-end recursion unterstützen, wobei die Rekursion in eine Iteration optimiert wird. Da kommen dann schnell und pfiffig zusammen.

Ah, Danke!

@adun: Das ist alles nicht so richtig korrekt. Endrekursion ist keine Spracheigenschaft, kein Feature, das man "unterstützen" könnte, und hat mit Schleifen erstmal nichts zu tun. Endrekursion ist eine immanente Eigenschaft einer Funktion, unabhängig von irgendeiner Sprache. Es gibt Sprachen, welche die Optimierung von Endrekursion in Schleifen in der Spezifikation festschreiben, und solche, die das nicht tun, es gibt Implementierungen, die Endrekursion optimieren, ohne das die Sprache das vorschreibt, und es gibt Implementierungen, die das nicht tun. Es gibt auch Sprachen, bei denen es gar nicht möglich ist, Endrekursion zu optimieren, bzw. bei denen man nicht feststellen kann, ob eine Funktion endrekursiv ist.

In jeder dieser Sprachen aber kann man Funktionen schreiben, die endrekursiv sind.

Jo hast natürlich recht, ich wollte schreiben "Es gibt aber Sprachimplementationen, die beispielsweise tail-end recursion optimisation unterstützen" das ist irgendwie untergegangen, müsste dann aber passen oder?

@adun: Ja. Erwähnen sollte man allerdings auch noch, dass sich keinesfalls jedes rekursive Problem auch endrekursiv formulieren lässt.

Hast du schon mal versucht in rekursive Datenstrukturen mit iterativen Funktionen zu arbeiten?

Das geht sehr gut (bei Perl hashes und arrays), man braucht halt nur einen Stack in der Funktion emulieren, was um Größenordnungen schneller sein kann als der Funktionsstack des Interpreters. Gerade heute habe ich auf Arbeit sowas programmiert, mal sehen ob ichs aus dem Gedächtnis wiederholen kann:

sub get_depth1stFlattener {
    my ($self) = @_;

    my @stack = ([ $self->root ]);

    return sub {{
        my $n = shift @{$stack[-1]};
        if ( !$n ) {
            pop @stack;
            @stack ? redo : return;
        } 
        if ( my @children = $n->children ) {
            push @stack, \@children;
        }
        return $n;
    }};
}

my $flattener = $obj->get_depth1stFlattener;

while ( my $node = $flattener->() ) {
    # do something with $node
}

Bei Hashes kann man mit each arbeiten, denn jeder Hash referenziert seinen eigenen Iterator, der so lange existiert wie das besitzende Hash-Objekt. Seine Position ist allein änderbar durch Zugriff via each/keys/values auf ebendiesen Hash.

Gruß, FLoH.tar

@The_Akki, @Maduser: Weder Fakultät noch Fibonacci-Zahlen sind IMHO gute Beispiele für den Sinn von Rekursion, weil man beides auch sehr gut iterativ ausdrücken kann.

@FLoH.tar: Natürlich geht das, aber man muss sich halt mit zusätzlichem Ballast herumschlagen.

Man muß immer abwägen zwischen Aufwand, Nutzen, Performance, Resourcen, ...

Es gibt Beispiele da kommt man um Rekursion nicht herum, z.B. (balancierte) binäre Bäume (Suche, Traversion usw.) sind iterativ ein unvergleichbar höherer Aufwand. Backtracing/Routing (z.B. beim Schaltungsentwurf) oder Pfadverfolgung ist auch ein gutes Beispiel wo Rekursion große Vorteile hat.

Die berühmten Beispiele mit Fakultät oder Fibonacci-Zahlen zeigen nicht die Power, die Rekursion hat. Die (mathematischen) Funktionen dahinter sind zu einfach und auch recht gut iterativ darstellbar. Da ist der Turm von Hanoi schon besser. 😉

@Lunar: Na, jetzt hatte ich gerade Endrekursionen als Mittel des Compilers verstanden. Chaot. 😛 😬

Ne, Spaß, wenn ich den Wikiartikel richtig verstanden habe, sind Endrekursionen die Rekursionsfunktionen, bei denen es keine Unterbrechung durch z.B. andere Funktionen mehr gibt, sodass ein optimierender Compiler die zu einer normalen Schleife umbauen kann, oder? Funktioniert das auch bei Interpretern?

@Alle danach: Da kann ich leider nicht mitreden, was Binärbäume, Hashes und die Türme von Hanoi sind, denn unser neuer Info-Lehrer hat erklärt, dass das Kultusministerium beschlossen hat, diese Themen für Irrelevant zu erklären und stattdessen so etwas wie endliche Automaten und formale Grammatik zum Abi vorzuschreiben. Ist das jetzt eher ein gutes oder ein schlechtes Omen? 😕

mfg

Sauer2

@DeJe: Vielleicht verstehe ich etwas anderes unter "Binärbaum", aber insbesondere die Suche in einem solchen Baum verlangt meines Erachtens keine Rekursion. Letztlich unterscheidet sich diese Operation schließlich wenig von der Iteration über eine verkettete Liste bzw. ein Feld.

@Sauer2: Bei rekursiven Funktionen kann man die Aufruf der eigenen Funktion in zwei Klassen unterteilen: Solche, bei denen danach nichts mehr passiert, und solche, bei denen danach noch Anweisungen stehen:

1
2
3
4
5

def foo(x):
    if x > 10:
        return x + foo(x+1)
    else:
        return foo(x+1)

Das Beispiel ist natürlich absolut unsinnig, zeigt aber das Prinzip: In der letzten Zeile wird der Rückgabewert des rekursiven Aufrufs direkt wieder zurückgegeben. Danach passiert nichts mehr. Zwei Zeilen drüber dagegen muss nach dem rekursiven Aufruf noch eine Addition durchgeführt werden. Rekursive Funktionen, bei denen alle Aufrufe so aussehen wie in der letzten Zeile des Beispiels, nennt man "endrekursiv", weil die Funktion immer entweder in ihrem eigenen rekursiven Aufruf oder ohne rekursiven Aufruf endet. Niemals aber wird der Rückgabewert eines rekursiven Aufrufs weiterverarbeitet.

Sprachen, in denen Funktionen statisch gebunden werden (sprich, "foo" bezeichnet immer und zu jedem Zeitpunkt die selbe Funktion), ermöglichen die Optimierung solcher endrekursiven Funktionen in Schleifen. Bei Sprachen, die Funktionen dynamisch zur Laufzeit binden (z.B. Python), ist das allerdings nicht möglich, da nicht garantiert ist, dass "foo" auf der n-ten Rekursionsebene immer noch die selbe Funktion bezeichnet.

Alles klar! Danke!

Lunar

Sprachen, in denen Funktionen statisch gebunden werden (sprich, "foo" bezeichnet immer und zu jedem Zeitpunkt die selbe Funktion), ermöglichen die Optimierung solcher endrekursiven Funktionen in Schleifen. Bei Sprachen, die Funktionen dynamisch zur Laufzeit binden (z.B. Python), ist das allerdings nicht möglich, da nicht garantiert ist, dass "foo" auf der n-ten Rekursionsebene immer noch die selbe Funktion bezeichnet.

Sehe da trotzdem keine Probleme warum das nicht optimiert werden könnte. Wenn eine Funktion einmal aufgerufen wurde dann läuft diese, auch wenn du diese nachträglich änderst sollte die bereits laufende funktion identisch bleiben. Und wenn dort eine endrekursion erkannt wird kann er es optimieren.

Letztendlich ist es sogar volkommen irrelevant ob diese ausgetauscht wird. Bei einem "return func(var)" am ende der funktion weiß der Interpreter das danach nichts mehr kommt. Die Endrekursion optimierung schaut auch nur so aus das nicht ständig ein neuer stack aufgebaut wird, und ein rückgabewert nicht durch hunderte von funktionen geschleift wird.

Solch eine Optimierung erinnert mich bei Perl z.b. auch an Methodenaufrufe in der vererbung. Man kann zur Laufzeit Methoden hinzufügen/austauschen. Dadurch kann sich die bedeutung von "$object->foo()" zur Laufzeit ändern weil "foo" etwas anderes wird. Trotzdem geht Perl deswegen nicht ständig immer wieder neu den Vererbungsbaum durch und sucht welche Methode gemeint ist. Es wird einmal gemacht, und solange man nichts hinzufügt oder austauscht wird das ergebniss gecached wodurch bei einem erneuerten aufruf nicht wieder erneut der vererbungsbaum durchgegangen werden muss.

EDIT:

Ich hab mal gelernt, dass der Aufruf von Funktionen und Methoden vergleichsweise lange dauert.

verglichen zu was?

Prädestiniert sind auch das Durchsuchen von Verzeichnissen oder das Durchwandern von Bäumen. Also überall da, wo man das Abbruchkriterium in nicht-rekursiver Schreibweise nicht genau formulieren kann.

Man kann jede Rekursion auch Itterativ darstellen. Und warum sollte man eine abbruchbindung nicht formulieren können?

Hast du schon mal versucht in rekursive Datenstrukturen mit iterativen Funktionen zu arbeiten? Oder bei rekursiven Problemen wie den Fibonacci-Zahlen.

Von "rekursiven Datenstrukturen" habe ich noch nie gehört. Höchstens vom komplexen. Ansonsten sind die Fibonacci Zahlen an sich kein rekursives problem. Sich die zwei letzten zahlen zu merken und diese zu addieren (itterrativ) ist sogar logischer als die voherige zahlen wieder neu zu berechnen indem ich die zahl davor und davovor neu berechne, und ich diese wieder neu berechne indem ich ...

Wenn ich dir ein blatt papier und ein stift in die hand drücke und sage "gebe mir die 10te fibonacci zahl" würdest du wohl auch die zahlen hintereinander aufschreiben bist du bei 10 angekommen bist anstatt es rekursiv zu berechnen.

Es gibt Beispiele da kommt man um Rekursion nicht herum, z.B. (balancierte) binäre Bäume (Suche, Traversion usw.) sind iterativ ein unvergleichbar höherer Aufwand. Backtracing/Routing (z.B. beim Schaltungsentwurf) oder Pfadverfolgung ist auch ein gutes Beispiel wo Rekursion große Vorteile hat.

Das man um rekursion nicht herum kommt würde ich nicht behaupten. Das eine Itteration mehr aufwand ist kann durchaus sein, das sie extrem viel komplizierter ist würde ich nicht behaupten. Eher noch ein Nachteil, bei Rekursion habe ich weniger Kontrolle über den ablauf während ich bei einer Iteration vollständige kontroller über den abfluss habe. Bei einer Suche kann ich Itterrativ z.B. vorgeben ob ich zuerst "deep first" suche. Oder bei einer Dateisuche erst dateien durchgehe und verzeichnisse hinten anschiebe. Das geht dort einwandfrei weil man den Stack bei einer Itteration selber verwaltet, bei einer rekursion wird der stack von der Programmiersprache verwaltet. kommt ein verzeichnis herein wird das bearbeitet.

Ansonsten, je nach aufwand, kannst du Iteratoren auch so programmieren das sie wieder rückgängig gehen können.

Und sehr viel besser ist das die Programmierung mit Iteratoren angenehmer ist. Bei einer Rekursiven Lösung übergibt man vielleicht callbacks and anonyme subs die auf events lauschen. Aber ist die rekursion am laufen habe ich danach wenig einfluss was dann passiert. Bei einem Iterator kann man sehr leicht programmieren das man z.B. nur bis zum ersten ergebniss sucht, und den Iterator dann verwerfen. All solche fälle in rekursiven aufrufen einzubauen/planen ist da eher deutlich komplexer. Von daher würde ich schon behaupten das eine Itrerative Lösung einer Rekursiven überlegen ist und sich der mehraufwand lohnt. Rekursion hat nur den Vorteil das es in manchen fällen einfach "einfacher" ist. Und manchmal brauch man auch einfach nicht die flexibilität.

Und zum Thema Backtracing. Die Regex Engine in Perl 5.8 war Rekursiv, mit perl 5.10 wurde sie Itterrativ, dadurch erhöhte sich die Performance und generell sind sachen die in Perl 5.8 zu einem stack overflow geführt haben jetzt lauffähig.