Können alle iterative Algorithmen rekursiv ausgedrückt werden?

StackOverflow https://stackoverflow.com/questions/2093618

Frage

Wenn nicht, ist es ein gutes Gegenbeispiel, das zeigt ein iterativer Algorithmus, für die es keine rekursiven Pendant existiert?

Wenn es der Fall, dass alle iterative Algorithmen rekursiv ausgedrückt werden kann, gibt es Fälle, in denen dies schwieriger zu tun?

Auch welche Rolle spielt das Programmiersprache Spiel in all dies? Ich kann mir vorstellen, dass Scheme-Programmierer haben eine andere Perspektive auf Iteration (= Schwanz-Rekursion) und Stackverbrauch als Java-Programmierer nur.

War es hilfreich?

Lösung

Es gibt einen einfachen Ad-hoc-Beweis dafür. Da Sie eine Turing-vollständige Sprache mit streng iterative Strukturen und Drehen der Sprach nur rekursive Strukturen mit aufbauen können, dann sind die beiden gleichkommt.

Andere Tipps

  

Können alle iterative Algorithmen rekursiv ausgedrückt werden?

Ja, aber der Beweis ist nicht interessant:

  1. Transformieren des Programms mit all ihrem Steuerstrom in eine einzige Schleife ein einzigen Fall, in dem Statement enthält jeder Zweig ist geradlinige Steuerung möglicherweise einschließlich fließen break, return, exit, raise, und so weiter. Führen Sie eine neue Variable (nennen wir es das „Programmzähler“), die die Case-Anweisung verwendet, die Block zu entscheiden, neben auszuführen.

    Diese Konstruktion wurde während der großen „structured-Programmierung Kriege“ der 1960er Jahre entdeckt, wenn die Menschen die relative Ausdruckskraft der verschiedenen Kontrollstrukturen stritten.

  2. Ersetzen die Schleife mit einer rekursiven Funktion, und Ersetzen jeden veränderbaren lokalen Variable mit einem Parameter dieser Funktion. Voilà! Iteration ersetzt durch Rekursion.

Dieses Verfahren beträgt einen Interpreter für die ursprüngliche Funktion zu schreiben. Wie man sich vorstellen kann, kommt es zu nicht lesbarem Code, und es ist nicht eine interessante Sache zu tun. Jedoch , einige der Techniken können für eine Person mit Hintergrund in imperativen Programmierung nützlich sein, die in einer funktionalen Sprache zum ersten Mal zu Programm lernen.

Wie Sie sagen, kann jeder iterativen Ansatz in eine „rekursive“ ein gedreht werden, und mit Endaufruf, wird der Stapel auch nicht explodieren. In der Tat :-), das eigentlich ist, wie Schema implementiert alle gängigen Formen des Looping. Beispiel in Schema: 

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

Obwohl hier die Funktion sieht iterativ, es recurses tatsächlich auf einem internen Lambda, die drei Parameter übernimmt, x, y und i, und die sich selbst mit neuen Werten bei jeder Iteration.

Hier ist eine Art und Weise, dass Funktion Makro erweitert sein könnte: 

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

Auf diese Weise wird die rekursive Natur visuell erkennbar.

Definition iterative als: 

function q(vars):
  while X:
    do Y

Kann übersetzt werden: 

 function q(vars):
    if X:
      do Y
      call q(vars)

Y in den meisten Fällen würde ein Zähler erhöht wird, die durch X getestet Dieser Variable wird zusammen in weitergegeben werden ‚vars‘ in irgendeiner Weise, wenn die rekursive Weg zu gehen.

Wie von Sockel in der ihrer Antwort können wir Beweise zeigen konstruieren, wie Rekursion und Iteration sind äquivalent und beide können sein verwendet, um das gleiche Problem zu lösen; aber obwohl wir wissen, die beiden sind äquivalent gibt es Nachteile übereinander zu verwenden.

In Sprachen, die für die Rekursion nicht optimiert sind, können Sie feststellen, dass ein Algorithmus unter Verwendung von Iteration Vorformen schneller als die rekursive ein und ebenso auch in optimierten Sprachen Sie können feststellen, dass ein Algorithmus Iteration in einer anderen Sprache läuft geschrieben mit schneller als die rekursive einer. Darüber hinaus kann es nicht offensichtlich, dass die Art und Weise von einem gegebenen Algorithmus geschrieben sein kehren im Vergleich zu Iteration und umge Verwendung Rekursion. Dies kann zu Code führen, der schwer zu was zu Wartbarkeit Fragen zu lesen.

Prolog ist rekursiv einzige Sprache, und man kann in ihm so ziemlich alles tun (ich schlage vor, Sie nicht zu tun, aber man kann:))

rekursive Lösungen ist in der Regel relativ ineffizient im Vergleich zu iterativen Lösungen. Es wird jedoch darauf hingewiesen, dass es einige Probleme gibt, die nur durch Rekursion und äquivalente iterative Lösung gelöst werden können, nicht existieren kann oder äußerst komplex Programm leicht (Beispiel hierfür ist Die Ackermann-Funktion kann nicht ohne Rekursion ausgedrückt werden ) Obwohl Rekursion elegant ist, einfach zu schreiben und verstehen.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top