Que doit inclure un algorithme récursif ?

L'algorithme de récursion (anglais : algorithme de récursion) en informatique fait référence à une méthode de résolution de problèmes en décomposant de manière répétée le problème en sous-problèmes similaires.

La méthode récursive peut être utilisée pour résoudre de nombreux problèmes informatiques, c'est donc un concept très important en informatique.

La plupart des langages de programmation prennent en charge l'appel automatique des fonctions. Dans ces langages, une fonction peut effectuer une récursivité en s'appelant elle-même. (Apprentissage recommandé : Tutoriel vidéo Web front-end)

La théorie informatique peut prouver que le rôle de la récursivité peut remplacer complètement les boucles, il est donc habituel d'utiliser la récursivité pour implémenter des boucles dans de nombreuses fonctions. langages de programmation (tels que Scheme) .

Programme récursif

Dans un langage de programmation qui prend en charge l'auto-appel, la récursivité peut être réalisée via un simple appel de fonction. Par exemple, un programme de calcul factoriel peut être défini mathématiquement comme. :

Ce programme peut être écrit en langage Scheme :

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

Combinateur à virgule fixe

Même un programme Si le langage ne prend pas en charge l'auto-appel, si la fonction est un objet de première classe (c'est-à-dire qu'elle peut être créée au moment de l'exécution et traitée comme une variable), la récursivité peut être générée via un combinateur à virgule fixe.

Le programme Scheme suivant n'utilise pas l'auto-appel, mais utilise un combinateur à virgule fixe appelé opérateur Z (anglais : Z combinator), il peut donc également atteindre l'objectif de récursivité.

(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/>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!