common-lisp => Рекурсия

замечания

Lisp часто используется в образовательных контекстах, где учащиеся учатся понимать и внедрять рекурсивные алгоритмы.

Производственный код, написанный на Common Lisp или переносимом коде, имеет несколько проблем с рекурсией: они не используют специфические для реализации функции, такие как оптимизация хвостовых вызовов , часто делая необходимым избегать рекурсии. В этих случаях реализации:

Обычно имеют ограничение глубины рекурсии из-за ограничений в размерах стека. Таким образом, рекурсивные алгоритмы будут работать только для данных ограниченного размера.
Не всегда обеспечивайте оптимизацию хвостовых вызовов, особенно в сочетании с операциями с динамическим охватом.
Только оптимизировать хвостовые звонки на определенных уровнях оптимизации.
Обычно не предусматривают оптимизацию хвостовых вызовов .
Обычно не предусматривают оптимизацию вызовов на определенных платформах. Например, реализации JVM могут не делать этого, поскольку сама JVM не поддерживает оптимизацию хвостового вызова .

Замена хвостовых вызовов с помощью переходов обычно затрудняет отладку; Добавление переходов приведет к тому, что фреймы стека станут недоступными в отладчике. В качестве альтернативы Common Lisp обеспечивает:

Конструкции итераций, такие как DO , DOTIMES , LOOP и другие
Функции более REDUCE порядка, такие как MAP , REDUCE и другие
Различные структуры управления, в том числе низкого уровня go to

Множество условий рекурсии 2

 (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

Рекурсивный шаблон 1 одиночная хвостовая рекурсия

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

Вычислить n-й номер Фибоначчи

;;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.
            )
        )
    )
)

Рекурсивно распечатать элементы списка

;;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))
        )
    )
)

Чтобы проверить это, запустите:

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

Результатом будет:

Вычислить факториал целого числа

Один простой алгоритм для реализации в качестве рекурсивной функции является факториалом.

;;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

Лицензировано согласно CC BY-SA 3.0

Не связан с Stack Overflow

common-lisp
Рекурсия

Поиск…