꼬리 재귀를 사용하여 쓸 수없는 문제가 있습니까?

StackOverflow https://stackoverflow.com/questions/1888702

문제

꼬리 재귀는 재귀 호출이 O (n)가 아닌 일정한 스택을 소비 할 수 있기 때문에 기능적 언어로 중요한 성능 최적화 스트라지기입니다.

단순히 꼬리 추방 스타일로 쓸 수없는 문제가 있습니까?

그렇다면 언젠가는 기능적 컴파일러와 통역사가 자동으로 변환을 수행 할만 큼 지능적 일 수 있습니까?

도움이 되었습니까?

해결책

예, 사실 당신 ~할 수 있다 코드를 가져 와서 모든 기능 호출과 모든 반환을 꼬리 호출을 변환하십시오. 당신이 끝나는 것은 연속 통과 스타일 또는 CPS라고합니다.

예를 들어 다음은 두 개의 재귀 호출을 포함하는 기능입니다.

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

이 기능을 연속 통과 스타일로 변환 한 경우 어떻게 보이는지가 있습니다.

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

추가 논쟁, ctn, 절차입니다 count-tree-cps 꼬리 집 돌아 오는 대신. (SDCVVC의 답변은 O (1) 공간에서 모든 것을 할 수 없다고 말합니다. 정확합니다. 여기서 각 연속은 메모리를 차지하는 폐쇄입니다.)

나는 전화를 변환하지 않았다 car 또는 cdr 또는 + 꼬리 집으로. 그것은 또한 할 수 있지만, 나는 그 잎 호출이 실제로 감소 될 것이라고 가정합니다.

이제 재미있는 부분을 위해. 닭 계획 실제로이 변환은 컴파일하는 모든 코드에서 변환합니다. 닭고기가 편집 한 절차 절대 돌아 오지 마십시오. 닭이 구현되기 전에 1994 년에 작성된 닭 계획이 왜이를 수행하는지 설명하는 고전적인 논문이 있습니다. 단점은 그 주장에 불과해서는 안됩니다. 파트 II : MTA의 Cheney

놀랍게도, 연속 패스 스타일은 JavaScript에서 상당히 일반적입니다. 당신은 그것을 사용할 수 있습니다 장기 실행 계산을 수행합니다, 브라우저의 "느린 스크립트"팝업을 피하십시오. 그리고 비동기 API에 매력적입니다. jQuery.get (xmlhttprequest 주변의 간단한 래퍼)는 분명히 연속 통과 스타일입니다. 마지막 인수는 기능입니다.

다른 팁

상호 재귀 함수의 모든 컬렉션이 꼬리 수반 기능으로 바뀔 수 있음을 관찰하는 것은 사실이지만 유용하지는 않습니다. 이 관찰은 1960 년대의 오래된 밤나무와 동등합니다. 모든 프로그램은 내부에 중첩 된 사례 문의 루프로 작성 될 수 있기 때문에 제어 흐름 구성을 제거 할 수 있습니다.

알아야 할 것은 분명히 꼬리 재수가 아닌 많은 기능이 추가로 테일 리퍼 시브 형태로 변환 될 수 있다는 것입니다. 축적 매개 변수. (이 변환의 극단적 인 버전은 CPS (Continuation-Passing Style)로 변환하는 것이지만 대부분의 프로그래머는 CPS의 출력이 읽기가 어렵다는 것을 알게됩니다.)

다음은 "재귀 적"(실제로 반복적이지만)이지만 꼬리 수익성이 아닌 함수의 예입니다.

factorial n = if n == 0 then 1 else n * factorial (n-1)

이 경우 곱셈이 발생합니다 ~ 후에 재귀 호출. 우리는 제품을 축적 매개 변수에 넣어 재귀적인 버전을 만들 수 있습니다.

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

내부 기능 f 테일 리커 셔드이며 단단한 루프로 컴파일합니다.

다음 차이점이 유용하다고 생각합니다.

  • 반복적이거나 재귀 프로그램에서 크기 문제를 해결합니다. n 먼저 해결함으로써 하나 크기의 하위 문제 n-1. 계승 기능을 계산하는 것은이 범주에 속하며 반복적으로 또는 재귀 적으로 수행 할 수 있습니다. (이 아이디어는 예를 들어, Fibonacci 기능을 일반화합니다. n-1 그리고 n-2 해결하다 n.)

  • 재귀 프로그램에서는 크기 문제를 해결합니다. n 먼저 해결함으로써 둘크기의 하위 문제 n/2. 또는 더 일반적으로 크기 문제를 해결합니다. n먼저 크기의 하위 문제를 해결함으로써 k 그리고 크기 중 하나 n-k, 어디 1 < k < n. QuickSort와 Mergesort는 이러한 종류의 문제의 두 가지 예입니다.이 문제는 재귀 적으로 쉽게 프로그래밍 될 수 있지만 반복적으로 프로그래밍하거나 꼬리 재귀 만 사용하기가 쉽지는 않습니다. (명시 적 스택을 사용하여 재귀를 시뮬레이션해야합니다.)

  • 동적 프로그래밍에서 크기 문제를 해결합니다. n 먼저 해결함으로써 모두모든 크기의 하위 문제 k, 어디 k<n. 런던 지하에서 한 지점에서 다른 지점에서 가장 짧은 경로를 찾는 것은 이런 종류의 문제의 예입니다. (London Underground는 다중 연결 그래프이며, 가장 짧은 경로가 1 정지 인 모든 지점을 먼저 찾아서 문제를 해결 한 다음 가장 짧은 경로가 2 정지 등이있는 등을 해결하여 문제를 해결합니다).

첫 번째 종류의 프로그램만이 있습니다 단순한 꼬리 수반 형태로 변환.

모든 재귀 알고리즘은 반복 알고리즘 (스택 또는 목록이 필요할 수 있음)으로 다시 작성할 수 있으며 반복 알고리즘은 항상 테일 리커스 알고리즘으로 다시 작성할 수 있으므로 재귀 솔루션을 꼬리 재주문 솔루션으로 어떻게 전환 할 수 있다고 생각합니다. .

(주석에서 Pascal Cuoq는 모든 알고리즘을 변환 할 수 있다고 지적합니다. 연속 패스 스타일.)

무언가가 꼬리 추방 적이라고해서 메모리 사용이 일정하다는 것을 의미하지는 않습니다. 그것은 단지 Call-Return 스택이 성장하지 않음을 의미합니다.

O (1) 공간 (공간 계층 정리)에서 모든 것을 할 수는 없습니다. 꼬리 재귀 사용을 고집하면 통화 스택을 인수 중 하나로 저장할 수 있습니다. 분명히 이것은 아무것도 바꾸지 않습니다. 내부적으로 어딘가에 통화 스택이 있으므로 단순히 명시 적으로 볼 수있게합니다.

그렇다면 언젠가는 기능적 컴파일러와 통역사가 자동으로 변환을 수행 할만 큼 지능적 일 수 있습니까?

이러한 전환은 공간 복잡성을 감소시키지 않습니다.

Pascal Cuoq가 언급했듯이 또 다른 방법은 사용하는 것입니다. CPS; 모든 통화는 재귀 적입니다.

나는 같은 생각을하지 않습니다 탁 꼬리 통화 만 사용하여 구현할 수 있습니다. (연속을 허용하지 않음)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top