재귀의 일반적인 개념을 알고 있습니다. 퀵 정렬 알고리즘을 연구하면서 꼬리 재귀 의 개념을 발견했습니다. 18:30 초에 MIT의 빠른 정렬 알고리즘 비디오 에서 교수는 이것이 꼬리 재귀 알고리즘이라고 말합니다. 꼬리 재귀가 실제로 무엇을 의미하는지 명확하지 않습니다.
누군가 적절한 예를 들어 개념을 설명 할 수 있습니까?
SO 커뮤니티에서 제공하는 일부 답변 여기 .
댓글
- 현재 상황에 대해 자세히 알려주세요. 꼬리 재귀 라는 용어를 발견했습니다. 링크? 인용?
- @ A.Schulz 컨텍스트에 대한 링크를 넣었습니다.
- " 꼬리 재귀 란 무엇입니까? " on stackoverflow
- @ajmartin 문제는 Stack Overflow 이지만 컴퓨터 과학 에 대한 주제에 확고하게 관련되어 있으므로 원칙적으로 컴퓨터 과학 은 더 나은 답을 제시해야합니다. 여기서는 ' 발생하지 않았지만 ' 더 나은 답변을 기대하며 여기에서 다시 요청해도됩니다. 괴짜, 이전 질문에 대해 언급 했어야하므로 사람들이 이미 말한 내용을 ' 반복하지 않도록 '.
- 또한 애매한 부분이나 이전 답변에 만족하지 않는 이유를 말해야합니다. 그래서 사람들이 좋은 답변을 제공하는 것 같지만 다시 질문하게 된 이유는 무엇입니까?
Answer
꼬리 재귀는 재귀 호출을 수행 한 후 호출 함수가 더 이상 계산을 수행하지 않는 특별한 재귀 사례입니다. 예를 들어
int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); }
함수는 꼬리 재귀 적이지만 (최종 명령은 재귀 호출이므로)이 함수는 꼬리 재귀 적이 아닙니다.
int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; }
재귀 호출이 반환 된 후 일부 계산을 수행하기 때문입니다.
꼬리 재귀는 일반 재귀보다 더 효율적으로 구현할 수 있기 때문에 중요합니다. 정상적인 재귀 호출을 할 때 반환 주소를 호출 스택에 푸시 한 다음 호출 된 함수로 점프해야합니다. 이는 재귀 호출의 깊이에서 크기가 선형 인 호출 스택이 필요함을 의미합니다. 꼬리 재귀가있을 때 우리는 재귀 호출에서 돌아 오자마자 즉시 반환 할 것임을 알고 있습니다. 따라서 반환되는 재귀 함수의 전체 체인을 건너 뛰고 원래 호출자에게 곧바로 돌아갈 수 있습니다. “모든 재귀 호출에 대해 호출 스택이 전혀 필요하지 않으며 최종 호출을 간단한 점프로 구현할 수 있으므로 공간을 절약 할 수 있습니다.
댓글
- " 즉, 모든 재귀 호출에 대해 호출 스택이 전혀 필요하지 않음 ' " 호출 스택은 항상있을 것입니다. 반환 주소를 호출 스택에 쓸 필요가 없습니다. 그렇지 않습니까?
- 그것은 어느 정도 계산 모델에 따라 다릅니다. 그러나 예, 실제 컴퓨터에서는 호출 스택이 여전히 존재하며 ' 그냥 사용하지 않습니다.
- 그것이 ' 마지막 for 루프에서 호출합니다. 따라서 위의 모든 계산을 수행하지만 일부는
def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)} - @ thed0ctor와 같은 for 루프에서 수행합니다.이 재귀는 수행하지 않습니다. ' t 종료.
Answer
간단히 말하면 꼬리 재귀는 컴파일러가 대체 할 수있는 재귀입니다. “goto”명령을 사용하여 재귀 호출을 수행하므로 컴파일 된 버전은 스택 깊이를 증가시킬 필요가 없습니다.
때때로 꼬리 재귀 함수를 디자인하려면 추가 매개 변수가있는 도우미 함수를 만들어야합니다.
예를 들어, 이것은 꼬리 재귀 함수가 아닙니다 :
int factorial(int x) { if (x > 0) { return x * factorial(x - 1); } return 1; } 그러나 이것은 꼬리- 재귀 함수 :
int factorial(int x) { return tailfactorial(x, 1); } int tailfactorial(int x, int multiplier) { if (x > 0) { return tailfactorial(x - 1, x * multiplier); } return multiplier; } 컴파일러가 다음과 같은 것을 사용하여 재귀 함수를 비 재귀 함수로 다시 작성할 수 있기 때문입니다 (의사 코드) :
int tailfactorial(int x, int multiplier) { start: if (x > 0) { multiplier = x * multiplier; x--; goto start; } return multiplier; } 컴파일러 규칙은 매우 간단합니다. “return thisfunction(newparameters);“를 찾으면 “
“입니다. 그러나 이것은 재귀 호출에서 반환 된 값이 직접 반환되는 경우에만 수행 할 수 있습니다.
함수에서 모든 재귀 호출을 이와 같이 대체 할 수 있다면 꼬리입니다. -재귀 함수.
답변
내 대답은 책 컴퓨터 프로그램의 구조 및 해석 . 나는이 책을 컴퓨터 과학자들에게 적극 추천합니다.
접근 A : 선형 재귀 프로세스
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 프로세스의 형태 접근법 A 는 다음과 같습니다.
(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 (* 1))))) (* 5 (* 4 (* 3 (* 2)))) (* 5 (* 4 (* 6))) (* 5 (* 24)) 120 접근 B : 선형 반복 프로세스
(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) 접근법 B 의 프로세스 모양은 다음과 같습니다.
(factorial 5) (fact-iter 1 1 5) (fact-iter 1 2 5) (fact-iter 2 3 5) (fact-iter 6 4 5) (fact-iter 24 5 5) (fact-iter 120 6 5) 120 선형 반복 프로세스 (접근 B)는 프로세스가 재귀 적 절차 임에도 불구하고 일정한 공간에서 실행됩니다. 이 접근 방식에서 설정된 변수는 모든 시점에서 프로세스의 상태를 정의한다는 점에 유의해야합니다. {product, counter, max-count}. 이것은 또한 꼬리 재귀가 컴파일러 최적화를 허용하는 기술입니다.
접근 A에는 기본적으로 지연된 작업의 체인 인 인터프리터가 유지 관리하는 더 많은 숨겨진 정보가 있습니다.
댓글
- ' 그냥
(1)대신(* 1)?
답변
꼬리 재귀 재귀 호출이 함수의 마지막 명령 인 재귀의 한 형태입니다 (꼬리 부분이 시작되는 위치). 또한 재귀 호출은 이전 값을 저장하는 메모리 셀에 대한 참조 (다른 참조)로 구성되어서는 안됩니다. 이러한 방식으로 우리는 이전 값에 신경 쓰지 않고 모든 재귀 호출에 대해 하나의 스택 프레임으로 충분합니다. 꼬리 재귀는 재귀 알고리즘을 최적화하는 한 가지 방법입니다. 다른 장점 / 최적화는 꼬리 재귀 알고리즘을 재귀 대신 반복을 사용하는 동등한 알고리즘으로 쉽게 변환 할 수 있다는 것입니다. 예, 퀵 정렬 알고리즘은 실제로 꼬리 재귀 적입니다.
QUICKSORT(A, p, r) if(p < r) then q = PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) 반복 버전은 다음과 같습니다.
QUICKSORT(A) p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) r = q - 1 p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) p = q + 1