common-lisp => Récursivité

Remarques

Lisp est souvent utilisé dans des contextes éducatifs, où les étudiants apprennent à comprendre et à implémenter des algorithmes récursifs.

Le code de production écrit en Common Lisp ou en code portable présente plusieurs problèmes de récursivité: ils n'utilisent pas de fonctionnalités spécifiques à l'implémentation telles que l' optimisation des appels de queue , ce qui rend souvent nécessaire d'éviter la récursivité. Dans ces cas, les implémentations:

A généralement une limite de profondeur de récursivité en raison des limites de taille des piles. Les algorithmes récursifs ne fonctionneront donc que pour des données de taille limitée.
Ne fournissez pas toujours une optimisation des appels de fin, en particulier en combinaison avec des opérations de portée dynamique.
Fournit uniquement une optimisation des appels de queue à certains niveaux d'optimisation.
Ne fournissez pas généralement une optimisation de l'appel de la queue .
Généralement, ne fournit pas d’optimisation de l’appel sur certaines plates-formes. Par exemple, les implémentations sur JVM peuvent ne pas le faire, car la JVM elle-même ne prend pas en charge l' optimisation des appels de queue .

Remplacer les appels de queue par des sauts rend généralement le débogage plus difficile; L'ajout de sauts entraînera l'indisponibilité des cadres de pile dans un débogueur. Comme alternative propose Common Lisp:

Constructions DOTIMES , comme DO , DOTIMES , LOOP et autres
Fonctions d'ordre supérieur, telles que MAP , REDUCE et autres
Diverses structures de contrôle, y compris à bas niveau, go to

Modèle de récursivité 2 multi-condition

 (defun fn (x)
      (cond (test-condition1 the-value1)
            (test-condition2 the-value2)
            ...
            ...
            ...
            (t (fn reduced-argument-x))))


 CL-USER 2788 > (defun my-fib (n)
                 (cond ((= n 1) 1)
                       ((= n 2) 1)
                       (t (+
                           (my-fib (- n 1))
                           (my-fib (- n 2))))))
MY-FIB

CL-USER 2789 > (my-fib 1)
1

CL-USER 2790 > (my-fib 2)
1

CL-USER 2791 > (my-fib 3)
2

CL-USER 2792 > (my-fib 4)
3

CL-USER 2793 > (my-fib 5)
5

CL-USER 2794 > (my-fib 6)
8

CL-USER 2795 > (my-fib 7)
13

Modèle de récursivité 1 récursivité simple à une seule condition

(defun fn (x)
  (cond (test-condition the-value)
        (t (fn reduced-argument-x))))

Calculez le nième nombre de Fibonacci

;;Find the nth Fibonacci number for any n > 0.
;; Precondition: n > 0, n is an integer. Behavior undefined otherwise.
(defun fibonacci (n)
    (cond
        (                                     ;; Base case.
             ;; The first two Fibonacci numbers (indices 1 and 2) are 1 by definition.
            (<= n 2)                          ;; If n <= 2
            1                                 ;; then return 1.
        )
        (t                                    ;; else
            (+                                ;; return the sum of
                                              ;; the results of calling 
                (fibonacci (- n 1))           ;; fibonacci(n-1) and
                (fibonacci (- n 2))           ;; fibonacci(n-2).
                                              ;; This is the recursive case.
            )
        )
    )
)

Imprime récursivement les éléments d'une liste

;;Recursively print the elements of a list
(defun print-list (elements)
    (cond
        ((null elements) '()) ;; Base case: There are no elements that have yet to be printed. Don't do anything and return a null list.
        (t
            ;; Recursive case
            ;; Print the next element.
            (write-line (write-to-string (car elements)))
            ;; Recurse on the rest of the list.
            (print-list (cdr elements))
        )
    )
)

Pour tester cela, lancez:

(setq test-list '(1 2 3 4))
(print-list test-list)

Le résultat sera:

Calculer la factorielle d'un nombre entier

Un algorithme facile à implémenter en tant que fonction récursive est factoriel.

;;Compute the factorial for any n >= 0. Precondition: n >= 0, n is an integer.
(defun factorial (n)
    (cond
        ((= n 0) 1) ;; Special case, 0! = 1
        ((= n 1) 1) ;; Base case, 1! = 1
        (t
            ;; Recursive case
            ;; Multiply n by the factorial of n - 1.
            (* n (factorial (- n 1)))
        )
    )
)

Modified text is an extract of the original Stack Overflow Documentation

Sous licence CC BY-SA 3.0

Non affilié à Stack Overflow

common-lisp
Récursivité

Recherche…