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

Question

Wenn nicht, gibt es ein gutes Gegenbeispiel, das einen iterativen Algorithmus zeigt, für den kein rekursives Gegenstück existiert?

Wenn alle iterativen Algorithmen rekursiv ausgedrückt werden können, gibt es Fälle, in denen dies schwieriger ist?

Welche Rolle spielt die Programmiersprache dabei? Ich kann mir vorstellen, dass Scheme-Programmierer die Iteration (= Tail-Recursion) und die Stack-Nutzung anders handhaben als Java-only-Programmierer.

Answer 1

Es gibt einen einfachen Ad-hoc-Beweis dafür. Da Sie eine vollständige Turing-Sprache mit streng iterativen Strukturen und einer vollständigen Turning-Sprache mit nur rekursiven Strukturen erstellen können, sind die beiden daher äquivalent.

Answer 2

Wie Sie sagen, kann jeder iterative Ansatz in einen "rekursiven" umgewandelt werden, und bei Tail-Aufrufen wird auch der Stapel nicht explodieren. :-) In der Tat implementiert Scheme tatsächlich alle gängigen Formen des Loopings. 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 iterative aussieht, ist 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 Möglichkeit, die 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))) 

diese Weise wird die rekursive Natur wird visuell erkennbar.

Answer 3

definieren 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 müssen entlang Diese Variable wird übergeben werden in 'Vars' in irgendeiner Weise, wenn die rekursive Route gehen.

Answer 4

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

Answer 5

Wie in der their answer durch Sockel stellten wir fest, Beweise konstruieren können zeigen, wie recursion und Iteration sind gleichwertig und können beide verwendet werden, um das gleiche Problem zu lösen; obwohl wir wissen, dass die beiden gleichwertig sind, gibt es jedoch Nachteile, wenn man die eine über der anderen verwendet. In Sprachen, die nicht für Rekursion optimiert sind, können Sie feststellen, dass ein Algorithmus, der Iteration verwendet, schneller als der rekursive Algorithmus ist und dass auch in optimierten Sprachen ein Algorithmus mit Iteration, der in einer anderen Sprache geschrieben ist, schneller läuft als der rekursiv. Darüber hinaus kann es keinen naheliegenden Weg geben, einen gegebenen Algorithmus unter Verwendung von Rekursion versus Iteration und umgekehrt zu schreiben. Dies kann zu schlecht lesbarem Code führen, der zu Problemen mit der Wartbarkeit führt.

Answer 6

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

Ja, aber der Beweis ist nicht interessant:

1. das Programm Transform mit all ihren Steuerstrom in einer einzigen Schleife jeder Zweig einen einzigen Fall Erklärung, in der enthalten ist geradliniger Steuerungsablauf möglich einschließlich break, return, 10, raise und so weiter. Führen Sie eine neue Variable ein (nennen Sie sie den "Programmzähler"), die die Case-Anweisung verwendet, um zu entscheiden, welcher Block als nächstes ausgeführt werden soll.

   Diese Konstruktion wurde während der großen "strukturierten Programmierkriege" der 1960er Jahre entdeckt, als die Leute die relative Ausdruckskraft verschiedener Kontrollflusskonstrukte diskutierten.

2. Ersetzen Sie die Schleife durch eine rekursive Funktion und ersetzen Sie jede veränderbare lokale Variable durch einen Parameter für diese Funktion. Voil & agrave ;! Iteration durch Rekursion ersetzt.

Dieser Vorgang entspricht dem Schreiben eines Interpreters für die ursprüngliche Funktion. Wie Sie sich vielleicht vorstellen können, führt dies zu unlesbarem Code und ist nicht interessant. Aber, einige der Techniken können für eine Person mit Hintergrund in imperativen Programmierung nützlich sein, die lernt, in einer funktionalen Sprache zum ersten Mal zu programmieren.

Answer 7

Rekursive Lösungen sind normalerweise relativ ineffizient im Vergleich zu iterativen Lösungen. Es ist jedoch anzumerken, dass es einige Probleme gibt, die nur durch Rekursion gelöst werden können und eine äquivalente iterative Lösung möglicherweise nicht existiert oder extrem komplex zu programmieren ist (Beispiel dafür ist Die Ackermann-Funktion kann nicht ohne Rekursion ausgedrückt werden) Obwohl Rekursionen sind elegant, einfach zu schreiben und zu verstehen.