Rekursion vs. Iteration

[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