Rekursion vs. Iteration

[Delphi-Laie]

Zitat von Daniel:

Zitat von Delphi-Laie:

Das Laufzeitverhalten ist dagegen eher mau, denn diese Baumstruktur des Prorgrammablaufes beim Aufrufen der rekursiv aufgerufenen Unterprogramme x. Ordnung führen mit ziemlicher Sicherheit zu mindestens exponentiellem Laufzeitverhalten (bei der Fakultät z.B. sogar zu hyperexponentiellem Wachstum).

Und warum das Laufzeitverhalten per se mau sei, kann ich aus Deinem Beitrag immer noch nicht entnehmen. Kannst Du die Formulierung "exponentielles Verhalten" präzisieren? Ich kenne z.B. exponentielles Wachstum - aber nicht exponentielles Verhalten.

Laufzeitverhalten schrieb ich.

Dann gehe mal einen rekursiven Algorithmus (im engeren Sinne, wie ich es ausführlich beschrieb), während er abläuft (also den Prozeß seines Ablaufes) durch: Die hierarchieniedrigsten Aufrufe sind die häufigsten! Konkret z.B. beim rekursiven Fibonacci: Fib(0) bzw. Fib(1) werden am häufigsten berechnet. Ziseliert man diesen Prozeß (graphisch), entsteht eine Baumstruktur. Und die Anzahl der Elemente von Bäumen ist - soweit ich weiß - exponentiell.

Edit: So allgemein gilt das doch nicht. Beim Quicksort ist das Laufzeitverhalten viel günstiger (logarithmisch), allerdings gibt es dort keine Mehrfachaufrufe: Was sortiert ist, wird nie wieder vom Algorithmus berührt (vielleicht ist das schon der Grund für die gute Komplexität?!), im Gegensatz zu den vielen Mehrfachberechnungen bei z.B. dem rekursiven Fibonacci. Das mehrmalige (konkret immer zweifache) Aufrufen von hierarchiegleichen Subprozessen (wie im Vorbeitrag ausgeführt) ist aber auch hier gegeben.

[JasonDX]

Zitat von Delphi-Laie:

Zurück zum Thema. Ich ließ mir absichtlich ein wenig Zeit für eine erneute Antwort. In dieser Diskussion wurde m.E. teilweise sogar erheblich aneinander vorbeigeredet. Richtig ist, rein formal und von der Definition her, daß Rekursion dadurch charakterisiert ist, daß sich Programmteile (immer Unterprogramme?) (ggf. wiederholt) selbst aufrufen. Rekursion und Iteration kann man in bestimmter Weise aufeinander abbilden (es gibt sozusagen eine Schnittmenge).

Diese Schnittmenge ist die Menge der derzeit berechenbaren Sprachen.

Zitat von Delphi-Laie:

Die folgliche Kongruenz, ja fast schon Äquivalenz von Rekursion und Iteration führe ich zu folgendem absurden Höhepunkt:

Delphi-Quellcode:

procedure rekursion;
begin
rekursion
end

versus

Delphi-Quellcode:

repeat 
until false

Gibt es einen substantiellen Unterschied zwischen beiden Programmteilen, insbesondere hinsichtlich ihres Laufverhaltens? Anscheinend nein, denn beides sind Endlosschleifen (abgesehen davon, daß erstere den Stack schnell überlaufen läßt).

Das Laufzeitverhalten eines Algorithmus ist nicht von der Art seiner Implementierung abhängig. Man kann relativ einfach aus einem iterativen Programm ein Rekursives erstellen, und umgekehrt. Mit selbem Laufzeitverhalten. Wenn du möchtest, kann ich dir zumindest die Idee dahinter erklären, auch wenns dann etwas theoretisch werden könnte.

Zitat von Delphi-Laie:

1. Jedes Element enthält sein eigenes Abbild in der jeweils 1. Subebene nur einmal. So etwas ist z.B. bei der rekursiven Fakultät oder - im materiellen Bereich - bei den russischen Puppen namens Matrjoschka der Fall. Ich bleibe dabei, daß eine solche Rekursion nur eine „Lightversion“ ist, da sie letztlich mit der Iteration konformläuft.

Was genau meinst du mit "konformlaufen"? Dass sich die Rekursion auf einen iterativen Ablauf zurückführen lässt? Dann ist jede Rekursion eine "Lightversion".

Zitat von Delphi-Laie:

3. Die Anzahl der Elemente (=Subprozesse) ist sicher größer als 1, so z.B. bei der rekursiven Fibonacciglied(er)berechnung.

Das hängt ganz von der Berechnungsmethode ab. Nimmt man die triviale Implementierung, so ist die Anzahl der direkten Unteraufrufe entweder 0 oder 2. Überträgt man diese Berechnung in eine iterative Form (ohne optimierungen, welche ja auch nicht für die Rekursion angewant wurden), so wird lediglich der Rekursionsbaum traversiert. Folglich hätte dann die iterative Variante das selbe Laufzeitverhalten.
Optimiert man die Algorithmen, so erhält man neue Berechnungsmethoden, und ein (hoffentlich) besseres Laufzeitverhalten. Aber es gelten immernoch die gleichen Bedingungen: Gibt es einen Algorithmus, der die n-te Fibonaccizahl in t(n) berechnet, so gibt es sowohl eine iterative, als auch eine rekursive Implementierung, die in Theta(t(n)) läuft.

Zitat von Delphi-Laie:

Erst in den Fällen 2 und 3 entfaltet die Rekursion ihr wahres Wesen: Sie ist elegant zu beschreiben (bzw. ist eine elgante Methode, Probleme zu lösen bzw. Problemlösungen darzustellen) und zu implementieren und führt zu kurzen, sicher auch gut wartbaren Quelltexten.

Das ist sogar auch bei 1. der Fall. Es gibt keine schönere Definition von Listen als die rekursive; insb. für theoretische Analysen.

Zitat von Delphi-Laie:

Das Laufzeitverhalten ist dagegen eher mau, denn diese Baumstruktur des Prorgrammablaufes beim Aufrufen der rekursiv aufgerufenen Unterprogramme x. Ordnung führen mit ziemlicher Sicherheit zu mindestens exponentiellem Laufzeitverhalten (bei der Fakultät z.B. sogar zu hyperexponentiellem Wachstum).

Die Laufzeit hängt von einem Algorithmus ab, nicht ob er rekursiv oder iterativ beschrieben wird. Beide sind gleichmächtige Beschreibungsformen. Der einzige Grund, warum Rekursion als langsamer empfunden wird als Iterationen ist der, dass 1. Die iterative Variante meist optimiert ist (Siehe bspw. Fibonacci), und 2. Ein Funktionsaufruf aufgrund der darunterliegenden Hardware länger braucht.

Zitat von Delphi-Laie:

Wollte man solche rekursiven Algorithem in adäquate iterative transformieren, so ist das entweder unmöglich (?) (1), sehr aufwendig (wie es hier jemand bezüglich Fibonacci andeutete)(2) oder nur unbefriedigend(3) (s. Quicksort, falls R. Sedgewicks Aussage immer noch aktuell ist) möglich.

Zu (1): Es ist (laut theoretischen Beweisen) immer möglich. Eine adäquate Implementierung wäre das iterative traversieren des Rekursionsbaumes. Inwiefern das aufwändig (2) ist, hängt eher von der Beschreibungssprache ab. Ob die Implementierung unbefriedigend (3) hängt in erster Linie von den Erwartungen ab. Lesbar ist eine solche generische Übertragung eher nicht; Aber das hängt in erster Linie von der Funktion ab, inwiefern diese eine lesbare iterative Implementierung erlaubt.


Was mir bisher eigentlich immer aufgefallen ist: Wenn ich mit Leuten über Rekursion ect. diskutiert habe, so waren das fast immer Leute, welche sich in erster Linie mit iterativen Programmiersprachen befasst haben. Vor 2 Jahren war ich rekursiven Implmentierungen zwar nicht abgeneigt, habe aber nur einen sehr scheuen und vorsichtigen Blick dahingewagt, immer im Hinterkopf, dass mir der dahinterliegende Code meinen Stack zumüllt.
Beginnt man, sich (gezwungenermaßen *g*) damit ordentlich außeinanderzusetzen, so lernt man damit umzugehen, und die Vorzüge kennenzulernen. Menschen, die die Ideen bspw. hinter Haskell, OCaml oder Lisp verstanden haben, musste ich noch nie von den Vorteilen von Rekursionen überzeugen - nur jene, die sich bisher noch nicht wirklich damit außeinandergesetzt haben.


greetz
Mike

[Delphi-Laie]

Zitat von JasonDX:

Zitat von Delphi-Laie:

1. Jedes Element enthält sein eigenes Abbild in der jeweils 1. Subebene nur einmal. So etwas ist z.B. bei der rekursiven Fakultät oder - im materiellen Bereich - bei den russischen Puppen namens Matrjoschka der Fall. Ich bleibe dabei, daß eine solche Rekursion nur eine „Lightversion“ ist, da sie letztlich mit der Iteration konformläuft.

Was genau meinst du mit "konformlaufen"? Dass sich die Rekursion auf einen iterativen Ablauf zurückführen lässt?

Zumindest die, die in Internetamateurenzyklopädie sicher aus gutem Grundes als „iterative“ Rekursion bezeichnet wird.

Zitat von JasonDX:

Dann ist jede Rekursion eine "Lightversion".

Das ist die entscheidende Frage. Jede Iteration läßt sich als Rekursion darstellen, denn letztlich rufen - in gewisser Weise - sich Schleifen auch nur selbst immer wieder auf.

Doch ist jede Rekursion auch als Iteration abbildbar? Dazu fehlen mir die Kenntnisse. Ist das schon bewiesen worden? In Robert Sedgewicks Standardwerk z.B. stand zur Quicksort, daß sich das nur unbefriedigend als Iteration darstellen/umsetzen läßt. Während der Implementation wurde mir rasch klar, daß mit der dort vorgestellten Quelltext letztlich nur die Stackhandhabung emuliert/simuliert wird, es also eine verkappte Rekursion ist.

Sollte die letzte Frage tatsächlich bejaht werden können, bliebe auf jeden Fall der Vorteil der kurzen, übersichtlichen Problem(lösungs)beschreibung sowie der Quelltexte mit gleichen Eigenschaften, zudem gut wart- und portierbarer Quelltexte.

Edit: Weiter oben schriebst Du, daß es laut „theoretischen Beweisen“ (Anmerkung: Derlei Beweise sind immer theoretisch) möglich sei. Das überlas ich zunächst.

[Codewalker]

Ich habe auf die Schnelle keine Quelle gefunden, die es explizit auf Iteration zurückführt, aber es gibt Funktionen, die insbesondere im Compilerbau Kopfschmerzen machen, nämlich nicht-primitiv-rekursive Funktionen (Ackermannfunktion, Busy Beaver, Sudanfunktion, etc.).
Ich meine mich zu erinnern, dass man die nicht einfach auf eine iterative Variante zurückführen kann.

[JasonDX]

Zitat von Delphi-Laie:

Zitat von JasonDX:

Dann ist jede Rekursion eine "Lightversion".

Das ist die entscheidende Frage. Jede Iteration läßt sich als Rekursion darstellen, denn letztlich rufen - in gewisser Weise - sich Schleifen auch nur selbst immer wieder auf.

So einfach ist es leider nicht - bspw. sind nicht Schleifen wirklich das Problem, sondern aufeinanderfolgende Befehle. Aber über die rein theoretische Definition von TMs lässt sich das ganze einfacher in rekursive Ausdrücke überführen.

Zitat von Delphi-Laie:

Doch ist jede Rekursion auch als Iteration abbildbar? Dazu fehlen mir die Kenntnisse. Ist das schon bewiesen worden?

In den 30ern von Alonzo Church, durch die Turingvollständigkeit von Lambdaausdrücken. Eine etwas einfachere und verständlichere Variante wäre die iterative Traversierung von Rekursionsbäumen. Im Endeffekt arbeitet deine CPU auch nur iterativ, und simuliert lediglich rekursive Aufrufe.

Zitat von Delphi-Laie:

In Robert Sedgewicks Standardwerk z.B. stand zur Quicksort, daß sich das nur unbefriedigend als Iteration darstellen/umsetzen läßt. Während der Implementation wurde mir rasch klar, daß mit der dort vorgestellten Quelltext letztlich nur die Stackhandhabung emuliert/simuliert wird, es also eine verkappte Rekursion ist.

Inwiefern eine Umsetzung unbefriedigend oder zufriedenstellend ist, hängt in erster Linie von den Möglichkeiten und Erwartungen ab. Allerdings ist das dann nicht eine "verkappte Rekursion", sondern eine möglichst allgemein anwendbare Überführung eines rekursiven Ausdrucks in eine iterative Form.

Zitat von Codewalker:

Ich habe auf die Schnelle keine Quelle gefunden, die es explizit auf Iteration zurückführt, aber es gibt Funktionen, die insbesondere im Compilerbau Kopfschmerzen machen, nämlich nicht-primitiv-rekursive Funktionen (Ackermannfunktion, Busy Beaver, Sudanfunktion, etc.).
Ich meine mich zu erinnern, dass man die nicht einfach auf eine iterative Variante zurückführen kann.

Nichtprimitiv-rekursive Funktionen bieten nur dann Probleme, wenn der Compiler versucht, diese zu optimieren. Ansonsten ist die Überführung in eine iterative Variante für den Compiler nicht sonderlich schwierig. Auch wenns widersprüchlich klingen mag, aber der CALL-Befehl auf CPU-Ebene ist rein iterativ.
Was den genannten Busy Beaver betrifft: Der ist gar nicht berechenbar, somit gibts weder eine iterative, noch ne rekursive Beschreibung dieser Funktion.

greetz
Mike

[Delphi-Laie]

Zitat von JasonDX:

Im Endeffekt arbeitet deine CPU auch nur iterativ, und simuliert lediglich rekursive Aufrufe.

Letztlich arbeitet eine (jede?!) CPU sogar nur sequentiell. Iterationen sind ja letztlich auch nur ein „Trick“, dem Prozessor immer und immer wieder das (fast) gleiche unterzuschieben.

Iterationen dienen der einfachen - hierarchiegleichen bzw. horizontalen - Wiederholung von Befehlen.

Rekursionen dienen der etas komplexeren, weil auf verschiedenen Hierarchieebenen befindlichen bzw. ablaufenden Wiederholung von Befehlen, sie sind sozusagen eine vertikale Iteration.

[mkinzler]

Wobei der Mechanismus der Rekursion fest in den Prozessor verankert ist ( Stack)

[negaH]

Zitat:

Letztlich arbeitet eine (jede?!) CPU sogar nur sequentiell.

Das ist eine Definitionsfrage. CPU=Central Processing Unit=Zentrale Recheneinheit. Wenn wir von einem Rechner=Computer ausgehen so ist die CPU der Kernbestandteil. Dieser könnte ein ASIC aber auch FPGA oder sogar ein ASIC mit internem FPGA sein. FPGAs arbeiten per se erstmal alles in parallel ab und nicht sequientiell. Wenn sequientiell dann weil es der Programmierer mit Hilfe eines Taktes so programmiert hat. Dh. relevante Teile eines Algorithmus können sehr wohl nicht-sequientiell also parallel ausgeführt werden.

Ergo: aus Sicht "Rekurson vs. Iteration", als Schreibweise eines Algorithmus in einer Programmiersprache, kann eine CPU diesen sehr wohl sequentiell wie eben auch nicht-sequentiell abarbeiten.

Beispiel: ein Algorithmus der auf der Boolschen Algebra basiert. Formal schreibt man diesen als Rekursive Formel und programmiert diesen auch exakt so in einem FPGA, in rekursiver Schreibweise. Die Synthese=Compiler, zerlegt diese Formel mit Hilfe der Boolschen Algebra über Matrizen in vollständig definiert Boolsche Ausdrücke. Daraus entsteht dann eine Verschaltung von elektronischen Gattern innerhalb des FPGAs. Man beschreibt also rekursiv das Verhalten einer Hardware. Obwohl also das Problem rekursiv formuliert wurde arbeitet die Elektronik im Zielsystem alles in parallel ab. Damit exitieren also keine Sprungbefehle, keine einzeln nacheinander abzuarbeitenden Befehlssequenzen und somit auch kein Stackframe und finally somit keine Benachteiligung in der Peformance und Resourcen der Schreibweisen "rekursiv vs. iterativ" eines Algos.

Gruß Hagen

[idefix2]

Zitat:

Beispiel: ein Algorithmus der auf der Boolschen Algebra basiert. Formal schreibt man diesen als Rekursive Formel und programmiert diesen auch exakt so in einem FPGA, in rekursiver Schreibweise

Also darunter kann ich mir überhaupt nichts vorstellen. Könntest Du mit einem Beispiel illustrieren, was du meinst?

Zitat:

Wobei der Mechanismus der Rekursion fest in den Prozessor verankert ist ( Stack)

Der Hardwarestack wird von rekursiven Prozedure verwendet, ebenso wie von nicht rekursiven Prozeduren. Der Stack selbst hat mit Rekursion nichts zu tun, sondern nur mit Prozeduraufrufen. Deshalb brauchen natürlich auch rekursive Prozeduren einen Stack.

[negaH]

Code:

  function XorVectorBits(Bits: std_logic_vector, Index: integer) return std_logic;
  variable 
    Result: std_logic;
  begin
    Result := Bits(Index);
    if Index < Bits'High then
      Result := Result xor XorVetorBits(Bits, Index +1);
    end if;
    return Result;
  end function; 

  function XorVextorBits(Bits: std_logic_vector) return std_logic;
  variable 
    Result: std_logic;
    Index: Intger;
  begin
    Result := '0';
    for Index in Bits'Range loop
      Result := Result xor Bits(Index);
    end loop;    
    return Result;
  end function;

Oben sieht man zwei Funktionen in VHDL, erstere ist rekusiv die zweite nutzt eine Schleife. Beide beschreiben ein Verhalten einer späteren Hardware.

Das Signal Bits stellt man sich zb. wie ein Datenbus vor der aus zb. 16 Datenleitungen besteht. Die Boolsche Funktion lautet in Worten: Verknüpfe alle Datenleitungen in Bits per XOR und gebe das Resultat, ein Bit, zurück.

Beides wird bei der Synthese in Hardware exakt identische Resultate erzeugen. Nämlich ein XOR Gatter mit Bits'Range Inputs und einem Output.

Ok, es dürfte klar sein das das ein sehr enfaches Beispiel ist und hier der Vorteil in der formalen Schreibweise einer Rekursion noch nicht zum tragen kommt.

Gruß Hagen