common-lisp
재귀

algorithm C Language C++ clojure Haskell Language Java Language GNU/Linux opencv Python Language vim
수색…


비고

Lisp은 학생들이 재귀 알고리즘을 이해하고 구현하는 것을 배우는 교육적 배경에서 종종 사용됩니다.

Common Lisp 또는 이식 가능한 코드로 작성된 생산 코드에는 재귀 호출과 관련하여 몇 가지 문제가 있습니다. 즉, 꼬리 호출 최적화 와 같은 구현 관련 기능을 사용하지 않고 종종 재귀를 피할 필요가 있습니다. 이 경우 구현 :

  • 일반적으로 스택 크기의 한계 로 인해 재귀 깊이 제한 이 있습니다. 따라서 재귀 알고리즘은 제한된 크기의 데이터에서만 작동합니다.
  • 항상 역동적 인 범위 작업과 함께 특히 꼬리 호출 최적화를 제공하지 마십시오.
  • 특정 최적화 수준에서 꼬리 호출 최적화 만 제공하십시오.
  • 보통 꼬리 전화 최적화를 제공하지 마십시오.
  • 대개 특정 플랫폼에서 테일 콜 최적화 를 제공하지 마십시오. 예를 들어, JVM 자체가 테일 호출 최적화를 지원하지 않기 때문에 JVM에서 구현하지 않을 수도 있습니다.

꼬리 호출을 점프로 대체하면 디버깅이 더 어려워집니다. 점프를 추가하면 스택 프레임이 디버거에서 사용할 수 없게됩니다. 대안으로 Common Lisp은 다음을 제공합니다 :

  • DO , DOTIMES , LOOP 및 기타와 같은 반복 구문
  • 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))))

피보나치 수를 계산하십시오.

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

정수의 계승을 계산하십시오.

재귀 함수로 구현하는 쉬운 알고리즘 중 하나는 계승 (factorial)입니다. 

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