[on lisp] 2.8 Tail-Recursion 꼬리재귀

2.8 Tail-Recursion

재귀는 자기자신을 호출하는 거다.
꼬리재귀는 자기자신을 호출할 때, 콜스택이 바닥나지 않도록 미리 일을 해놓는다고 한다.
아래 내용은 꼬리재귀가 아니다.

(defun our-length (lst)
  (if (null lst)
      0
    (1+ (our-length (cdr lst)))))

왜냐하면 재귀호출에서 리턴을 할 때, 1+이라는 함수에게 넘겨야 하기 때문이다.
아래는 꼬리재귀다.

(defun our-find-if (fn lst)
  (if (funcall fn (car lst))
      (car lst)
   (our-find-if fn (cdr lst))))

왜냐하면 재귀호출의 값이 즉시 리턴되기 때문이다.

꼬리재귀는 꽤나 중요한데, 이런 재귀호출을 루프로 변환해주도록 컴파일러들이 디자인되어 있다.
이런 우아한 재귀호출을 사용하면서도 함수를 호출하는 오버헤드를 느낄 수 없게 된다.
이정도의 최적화면 재귀호출가 루프를 대신할 정도는 된다고 할만 하다.

꼬리재귀가 아닌 함수는 종종 꼬리재귀로 변형하기 위해서 accumulator를 내부에 넣어서 상태를 기록하도록 한다.

(defun our-length (lst)
  (labels ((rec (lst acc)
                (if (null lst)
        acc
     (rec (cdr lst) (1+ acc))))))
  (rec lst 0))

여기 acc를 보면 계속 1+로 1을 더하면서 재귀를 실행한다. 이렇게 누산기를 넣어서 재귀를 하는 거다.
그리고 acc를 마지막에 리턴할 거다.
커먼리습 컴파일러는 이런 꼬리재귀를 최적화 할 수 있다. 하지만 이게 디폴트인 경우는 드믈다.
파일 맨 위에 아래 내용을 적어라.

(proclaim '(optimize speed))

꼬리재귀와 타입선언으로 커먼리습 컴파일러는 코드가 C언어만큼 (혹은 더 빠르게) 코드를 생성한다.
Richard Gabriel 이라는 사람이 소개한 예제를 적는다.
1부터 n까지 더하는 함수이다.

(defun triangle (n)
  (labels ((tri (c n)
  (declare (type fixnum n c))
  (if (zerop n)
      c
    (tri (the fixnum (+ n c))
         (the fixnum (- n 1))))))
    (tri 0 n)))
(print (triangle 10))

아래처럼 acc를 이용하여 꼬리재귀를 이용한다.
declare,type을 이용하여 타입을 지정하는 것으로 보인다.