Was muss ein rekursiver Algorithmus beinhalten?

Rekursionsalgorithmus (englisch: Rekursionsalgorithmus) bezeichnet in der Informatik eine Methode zur Lösung von Problemen durch wiederholte Zerlegung des Problems in ähnliche Teilprobleme.

Die rekursive Methode kann zur Lösung vieler Informatikprobleme verwendet werden und ist daher ein sehr wichtiges Konzept in der Informatik.

Die meisten Programmiersprachen unterstützen den Selbstaufruf von Funktionen. In diesen Sprachen kann eine Funktion eine Rekursion durchführen, indem sie sich selbst aufruft. (Empfohlenes Lernen: Web-Frontend-Video-Tutorial)

Die Computertheorie kann beweisen, dass die Rolle der Rekursion Schleifen vollständig ersetzen kann. Daher ist es üblich, Rekursion zu verwenden, um Schleifen in vielen Funktionen zu implementieren Programmiersprachen (wie Scheme).

Rekursives Programm

In einer Programmiersprache, die Selbstaufruf unterstützt, kann die Rekursion durch einen einfachen Funktionsaufruf erreicht werden. Beispielsweise kann ein Programm zur Berechnung von Fakultäten mathematisch definiert werden als :

Dieses Programm kann in der Scheme-Sprache geschrieben werden:

(define (factorial n)  (if (= n 0)      1      (* n (factorial (- n 1)))))<br/>

Fixkommakombinator

Sogar ein Programm Wenn die Sprache den Selbstaufruf nicht unterstützt und die Funktion ein erstklassiges Objekt ist (dh zur Laufzeit erstellt und als Variable behandelt werden kann), kann eine Rekursion über einen Festkomma-Kombinator generiert werden.

Das folgende Scheme-Programm verwendet keinen Selbstaufruf, sondern einen Festkomma-Kombinator namens Z-Operator (englisch: Z-Kombinator), sodass es auch den Zweck der Rekursion erreichen kann.

(define Z  (lambda (f)    ((lambda (recur) (f (lambda arg (apply (recur recur) arg))))     (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact  (Z (lambda (f)       (lambda (n)         (if (<= n 0)             1             (* n (f (- n 1))))))))<br/>

Das obige ist der detaillierte Inhalt vonWas muss ein rekursiver Algorithmus beinhalten?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!