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)
Результатом будет:
1
2
3
4
Вычислить факториал целого числа
Один простой алгоритм для реализации в качестве рекурсивной функции является факториалом.
;;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