꼬리 재귀 란 무엇입니까?

질문자 :Community Wiki

lisp를 배우기 시작하면서 나는 tail-recursive 라는 용어를 접하게 되었습니다. 정확히 무엇을 의미합니까?

처음 N개의 자연수를 더하는 간단한 함수를 고려하십시오. (예: sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15 ).

다음은 재귀를 사용하는 간단한 JavaScript 구현입니다.

 function recsum(x) { if (x === 0) { return 0; } else { return x + recsum(x - 1); } }

recsum(5) 를 호출한 경우 JavaScript 인터프리터는 다음을 평가합니다.

 recsum(5) 5 + recsum(4) 5 + (4 + recsum(3)) 5 + (4 + (3 + recsum(2))) 5 + (4 + (3 + (2 + recsum(1)))) 5 + (4 + (3 + (2 + (1 + recsum(0))))) 5 + (4 + (3 + (2 + (1 + 0)))) 5 + (4 + (3 + (2 + 1))) 5 + (4 + (3 + 3)) 5 + (4 + 6) 5 + 10 15

JavaScript 인터프리터가 실제로 합계 계산 작업을 시작하기 전에 모든 재귀 호출이 완료되어야 하는 방법에 유의하십시오.

다음은 동일한 함수의 꼬리 재귀 버전입니다.

 function tailrecsum(x, running_total = 0) { if (x === 0) { return running_total; } else { return tailrecsum(x - 1, running_total + x); } }

tailrecsum(5) (기본 두 번째 인수로 인해 tailrecsum(5, 0) 이 됨)을 호출한 경우 발생할 이벤트 시퀀스입니다.

 tailrecsum(5, 0) tailrecsum(4, 5) tailrecsum(3, 9) tailrecsum(2, 12) tailrecsum(1, 14) tailrecsum(0, 15) 15

꼬리 재귀의 경우 재귀 호출을 평가할 때마다 running_total 이 업데이트됩니다.

참고: 원래 답변은 Python의 예제를 사용했습니다. Python 인터프리터가 꼬리 호출 최적화를 지원하지 않기 때문에 이것들은 JavaScript로 변경되었습니다. 그러나 꼬리 호출 최적화는ECMAScript 2015 사양의 일부 이지만 대부분의 JavaScript 인터프리터 는 이를 지원하지 않습니다 .

Lorin Hochstein

전통적인 재귀 에서 일반적인 모델은 재귀 호출을 먼저 수행한 다음 재귀 호출의 반환 값을 가져와 결과를 계산하는 것입니다. 이런 식으로 모든 재귀 호출에서 돌아올 때까지 계산 결과를 얻을 수 없습니다.

꼬리 재귀 에서는 먼저 계산을 수행한 다음 재귀 호출을 실행하여 현재 단계의 결과를 다음 재귀 단계로 전달합니다. 그 결과 마지막 문이 (return (recursive-function params)) 됩니다. 기본적으로 주어진 재귀 단계의 반환 값은 다음 재귀 호출의 반환 값과 동일합니다 .

그 결과 다음 재귀 단계를 수행할 준비가 되면 현재 스택 프레임이 더 이상 필요하지 않습니다. 이것은 약간의 최적화를 허용합니다. 사실, 적절하게 작성된 컴파일러를 사용하면 꼬리 재귀 호출 이 있는 스택 오버플로 스니커가 없어야 합니다. 다음 재귀 단계를 위해 현재 스택 프레임을 재사용하기만 하면 됩니다. 나는 Lisp가 이것을 할 것이라고 확신합니다.

user316

중요한 점은 꼬리 재귀가 본질적으로 루핑과 동일하다는 것입니다. 컴파일러 최적화의 문제가 아니라 표현력에 대한 근본적인 사실입니다. 이것은 두 가지 방법으로 진행됩니다. 양식의 모든 루프를 사용할 수 있습니다.

 while(E) { S }; return Q

여기서 E 와 Q 는 표현식이고 S 는 일련의 명령문이며 꼬리 재귀 함수로 변환합니다.

 f() = if E then { S; return f() } else { return Q }

물론 E , S 및 Q 는 일부 변수에 대해 흥미로운 값을 계산하기 위해 정의되어야 합니다. 예를 들어, 루프 함수

 sum(n) { int i = 1, k = 0; while( i <= n ) { k += i; ++i; } return k; }

꼬리 재귀 함수와 동일합니다.

 sum_aux(n,i,k) { if( i <= n ) { return sum_aux(n,i+1,k+i); } else { return k; } } sum(n) { return sum_aux(n,1,0); }

(이러한 꼬리 재귀 함수를 매개변수가 더 적은 함수로 "래핑"하는 것은 일반적인 함수 관용구입니다.)

Chris Conway

Programming in Lua 책에서 발췌한 이 발췌문은 적절한 꼬리 재귀를 만드는 방법 (Lua에서도 있지만 Lisp에도 적용되어야 함)과 이것이 더 나은 이유를 보여줍니다.

꼬리 호출 [꼬리 재귀]는 호출로 위장한 일종의 고토입니다. 꼬리 호출은 함수가 다른 함수를 마지막 작업으로 호출할 때 발생하므로 다른 할 일이 없습니다. 예를 들어 다음 코드에서 g 에 대한 호출은 꼬리 호출입니다.

 function f (x) return g(x) end

f 가 g 호출한 후에는 다른 할 일이 없습니다. 이러한 상황에서 프로그램은 호출된 함수가 종료될 때 호출하는 함수로 돌아갈 필요가 없습니다. 따라서 꼬리 호출 후 프로그램은 호출 함수에 대한 정보를 스택에 보관할 필요가 없습니다. ...

적절한 테일 호출은 스택 공간을 사용하지 않기 때문에 프로그램이 만들 수 있는 "중첩된" 테일 호출의 수에는 제한이 없습니다. 예를 들어, 임의의 숫자를 인수로 사용하여 다음 함수를 호출할 수 있습니다. 스택을 오버플로하지 않습니다.

 function foo (n) if n > 0 then return foo(n - 1) end end

... 앞서 말했듯이 테일 콜은 일종의 goto입니다. 따라서 Lua에서 적절한 꼬리 호출을 매우 유용한 응용 프로그램은 상태 머신을 프로그래밍하는 것입니다. 이러한 응용 프로그램은 각 상태를 함수로 나타낼 수 있습니다. 상태를 변경하는 것은 특정 기능으로 이동(또는 호출)하는 것입니다. 예를 들어 간단한 미로 게임을 생각해 봅시다. 미로에는 북쪽, 남쪽, 동쪽 및 서쪽의 최대 4개의 문이 있는 여러 개의 방이 있습니다. 각 단계에서 사용자는 이동 방향을 입력합니다. 해당 방향에 문이 있으면 해당 방으로 이동합니다. 그렇지 않으면 프로그램에서 경고를 인쇄합니다. 목표는 초기 방에서 최종 방으로 가는 것입니다.

이 게임은 현재 방이 상태인 전형적인 상태 머신입니다. 우리는 각 방에 대해 하나의 기능으로 이러한 미로를 구현할 수 있습니다. 우리는 한 방에서 다른 방으로 이동할 때 꼬리 호출을 사용합니다. 4개의 방이 있는 작은 미로는 다음과 같이 보일 수 있습니다.

 function room1 () local move = io.read() if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end end function room2 () local move = io.read() if move == "south" then return room4() elseif move == "west" then return room1() else print("invalid move") return room2() end end function room3 () local move = io.read() if move == "north" then return room1() elseif move == "east" then return room4() else print("invalid move") return room3() end end function room4 () print("congratulations!") end

따라서 다음과 같이 재귀 호출을 할 때 볼 수 있습니다.

 function x(n) if n==0 then return 0 n= n-2 return x(n) + 1 end

재귀 호출이 수행된 후 해당 함수에서 여전히 수행할 작업(1 추가)이 있기 때문에 꼬리 재귀가 아닙니다. 매우 높은 숫자를 입력하면 스택 오버플로가 발생할 수 있습니다.

Hoffmann

일반 재귀를 사용하여 각 재귀 호출은 호출 스택에 다른 항목을 푸시합니다. 재귀가 완료되면 앱은 각 항목을 다시 아래로 완전히 꺼야 합니다.

꼬리 재귀를 사용하면 언어에 따라 컴파일러가 스택을 하나의 항목으로 축소할 수 있으므로 스택 공간을 절약할 수 있습니다. 재귀 쿼리가 크면 실제로 스택 오버플로가 발생할 수 있습니다.

기본적으로 꼬리 재귀는 반복에 최적화될 수 있습니다.

FlySwat

전문 용어 파일에는 꼬리 재귀의 정의에 대해 다음과 같이 나와 있습니다.

꼬리 재귀 /n./

아직 질리지 않는다면 꼬리 재귀를 참조하십시오.

Pat

말로 설명하는 대신 예를 들어보겠습니다. 이것은 계승 함수의 Scheme 버전입니다:

 (define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1)))))

다음은 꼬리 재귀인 계승 버전입니다.

 (define factorial (letrec ((fact (lambda (x accum) (if (= x 0) accum (fact (- x 1) (* accum x)))))) (lambda (x) (fact x 1))))

첫 번째 버전에서 사실에 대한 재귀 호출이 곱셈 표현식에 제공되므로 재귀 호출을 수행할 때 상태를 스택에 저장해야 한다는 것을 알 수 있습니다. 꼬리 재귀 버전에는 재귀 호출의 값을 기다리는 다른 S-식이 없으며 더 이상 수행할 작업이 없으므로 상태를 스택에 저장할 필요가 없습니다. 일반적으로 Scheme 꼬리 재귀 함수는 일정한 스택 공간을 사용합니다.

Kyle Cronin

꼬리 재귀는 재귀 알고리즘의 마지막 논리 명령에서 마지막에 있는 재귀 호출을 나타냅니다.

일반적으로 재귀에서는 재귀 호출을 중지하고 호출 스택을 팝하기 시작 하는 기본 케이스가 있습니다. 고전적인 예를 사용하기 위해 Lisp보다 C-ish가 더 많지만 계승 함수는 꼬리 재귀를 보여줍니다. 재귀 호출은 기본 케이스 조건을 확인한 후 발생합니다.

 factorial(x, fac=1) { if (x == 1) return fac; else return factorial(x-1, x*fac); }

factorial에 대한 초기 호출은 factorial(n) 이 될 것입니다. 여기서 fac=1 (기본값)이고 n은 계승을 계산할 숫자입니다.

Peter Meyer

이는 스택에서 명령어 포인터를 푸시할 필요 없이 단순히 재귀 함수의 맨 위로 점프하여 실행을 계속할 수 있음을 의미합니다. 이것은 함수가 스택을 오버플로하지 않고 무한히 재귀하도록 합니다.

스택 프레임이 어떻게 생겼는지에 대한 그래픽 예제가 있는 주제에 대한 블로그 게시물을 작성했습니다.

Chris Smith

다음은 두 함수를 비교하는 빠른 코드입니다. 첫 번째는 주어진 숫자의 계승을 찾는 전통적인 재귀입니다. 두 번째는 꼬리 재귀를 사용합니다.

매우 간단하고 직관적으로 이해할 수 있습니다.

재귀 함수가 꼬리 재귀인지 여부를 쉽게 알 수 있는 방법은 기본 사례에서 구체적인 값을 반환하는지 여부입니다. 1 또는 true 또는 이와 유사한 것을 반환하지 않음을 의미합니다. 메서드 매개변수 중 하나의 변형을 반환할 가능성이 높습니다.

또 다른 방법은 재귀 호출에 추가, 산술, 수정 등이 없는지 확인하는 것입니다. 이는 순수한 재귀 호출에 불과하다는 의미입니다.

 public static int factorial(int mynumber) { if (mynumber == 1) { return 1; } else { return mynumber * factorial(--mynumber); } } public static int tail_factorial(int mynumber, int sofar) { if (mynumber == 1) { return sofar; } else { return tail_factorial(--mynumber, sofar * mynumber); } }

Community Wiki

tail call recursion 를 이해하는 가장 좋은 방법 은 마지막 호출 (또는 꼬리 호출)이 함수 자체인 특수한 경우의 재귀입니다.

Python에서 제공되는 예제 비교:

 def recsum(x): if x == 1: return x else: return x + recsum(x - 1)

^재귀

 def tailrecsum(x, running_total=0): if x == 0: return running_total else: return tailrecsum(x - 1, running_total + x)

^꼬리 재귀

일반 재귀 버전에서 볼 수 있듯이 코드 블록의 최종 호출은 x + recsum(x - 1) 입니다. recsum 메서드를 호출한 후 x + .. 라는 또 다른 작업이 있습니다.

그러나 꼬리 재귀 버전에서 코드 블록의 최종 호출(또는 꼬리 호출)은 tailrecsum(x - 1, running_total + x) 입니다. 즉, 마지막 호출이 메서드 자체에 수행되고 그 이후에는 작업이 수행되지 않음을 의미합니다.

기본 VM이 꼬리 위치(함수에서 평가되는 마지막 표현식)에서 자신을 호출하는 함수를 볼 때 현재 스택 프레임을 제거하기 때문에 여기에서 볼 수 있는 꼬리 재귀가 메모리를 증가시키지 않기 때문에 이 점이 중요합니다. 꼬리 호출 최적화(TCO)로 알려져 있습니다.

편집하다

주의 위의 예는 런타임이 TCO를 지원하지 않는 Python으로 작성되었음을 명심하십시오. 이것은 요점을 설명하기 위한 예시일 뿐입니다. TCO는 Scheme, Haskell 등과 같은 언어에서 지원됩니다.

Community Wiki

Java에서 피보나치 함수의 가능한 꼬리 재귀 구현은 다음과 같습니다.

 public int tailRecursive(final int n) { if (n <= 2) return 1; return tailRecursiveAux(n, 1, 1); } private int tailRecursiveAux(int n, int iter, int acc) { if (iter == n) return acc; return tailRecursiveAux(n, ++iter, acc + iter); }

이것을 표준 재귀 구현과 대조하십시오.

 public int recursive(final int n) { if (n <= 2) return 1; return recursive(n - 1) + recursive(n - 2); }

jorgetown

저는 Lisp 프로그래머는 아니지만 이것이 도움이 될 것이라고 생각합니다.

기본적으로 재귀 호출이 마지막으로 수행되는 프로그래밍 스타일입니다.

Matt Hamilton

재귀 함수는 스스로 호출 하는 함수입니다.

프로그래머는 최소한의 코드를 사용하여 효율적인 프로그램을 작성할 수 있습니다.

단점은 제대로 작성하지 않으면 무한 루프 및 기타 예기치 않은 결과가 발생할 수 있다는 것입니다.

단순 재귀 함수와 꼬리 재귀 함수에 대해 설명하겠습니다.

단순 재귀 함수 를 작성하려면

1. 고려해야 할 첫 번째 요점은 언제 루프에서 나올지 결정해야 하는 때입니다. 이 루프는 if 루프입니다.
2. 두 번째는 우리만의 기능이 있다면 어떤 과정을

주어진 예에서 :

 public static int fact(int n){ if(n <=1) return 1; else return n * fact(n-1); }

위의 예에서

 if(n <=1) return 1;

루프를 종료할 때 결정적인 요소입니다.

 else return n * fact(n-1);

실제 처리가 완료되는지 여부

이해하기 쉽게 하나씩 풀어보도록 하겠습니다.

fact(4) 실행하면 내부적으로 어떤 일이 일어나는지 봅시다.

1. 대체 n=4

 public static int fact(4){ if(4 <=1) return 1; else return 4 * fact(4-1); }

If 가 간다, 그래서 루프는 실패 else 루프는 반환 있도록 4 * fact(3)

2. 스택 메모리에는 4 * fact(3)

   대체 n=3

 public static int fact(3){ if(3 <=1) return 1; else return 3 * fact(3-1); }

If 루프 실패가 간다 그래서 else 루프

3 * fact(2) 반환합니다.

우리가 ```4 * fact(3)``를 호출했다는 것을 기억하십시오.

fact(3) = 3 * fact(2)

지금까지 스택에는 4 * fact(3) = 4 * 3 * fact(2)

3. 스택 메모리에는 4 * 3 * fact(2)

   대체 n=2

 public static int fact(2){ if(2 <=1) return 1; else return 2 * fact(2-1); }

If 루프 실패가 간다 그래서 else 루프

2 * fact(1) 반환합니다.

4 * 3 * fact(2) 호출했음을 기억하십시오.

fact(2) = 2 * fact(1) 대한 출력

지금까지 스택은 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. 스택 메모리에는 4 * 3 * 2 * fact(1)

   대체 n=1

 public static int fact(1){ if(1 <=1) return 1; else return 1 * fact(1-1); }

If 루프는 사실이다

1 을 반환합니다

4 * 3 * 2 * fact(1) 호출했다는 것을 기억하십시오.

fact(1) = 1 의 출력 = 1

지금까지 스택은 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

마지막으로, fact(4) = 4 * 3 * 2 * 1 = 24의 결과

꼬리 재귀 는

 public static int fact(x, running_total=1) { if (x==1) { return running_total; } else { return fact(x-1, running_total*x); } }

1. 대체 n=4

 public static int fact(4, running_total=1) { if (x==1) { return running_total; } else { return fact(4-1, running_total*4); } }

If 가 간다, 그래서 루프가 실패 할 else 루프 있도록 반환 fact(3, 4)

2. 스택 메모리에는 fact(3, 4)

   대체 n=3

 public static int fact(3, running_total=4) { if (x==1) { return running_total; } else { return fact(3-1, 4*3); } }

If 루프 실패가 간다 그래서 else 루프

그래서 그것은 사실을 반환합니다 fact(2, 12)

2. 스택 메모리에는 fact(2, 12)

   대체 n=2

 public static int fact(2, running_total=12) { if (x==1) { return running_total; } else { return fact(2-1, 12*2); } }

If 루프 실패가 간다 그래서 else 루프

그래서 그것은 사실을 반환합니다 fact(1, 24)

3. 스택 메모리에는 fact(1, 24)

   대체 n=1

 public static int fact(1, running_total=24) { if (x==1) { return running_total; } else { return fact(1-1, 24*1); } }

If 루프는 사실이다

running_total 을 반환합니다.

running_total = 24 의 출력

마지막으로, fact(4,1) = 24의 결과

Community Wiki

다음은 꼬리 재귀를 사용하여 계승을 수행하는 Common Lisp 예제입니다. 스택이 없는 특성으로 인해 엄청나게 큰 계승 계산을 수행할 수 있습니다.

 (defun ! (n &optional (product 1)) (if (zerop n) product (! (1- n) (* product n))))

그런 다음 재미를 위해 시도할 수 있습니다 (format nil "~R" (! 25))

Community Wiki

간단히 말해서, 꼬리 재귀는 재귀 호출을 기다릴 필요가 없도록 함수 의 마지막 명령문으로 재귀 호출을 갖습니다.

따라서 이것은 꼬리 재귀입니다. 즉, N(x - 1, p * x)는 for-loop(factorial)에 최적화될 수 있다는 것을 컴파일러가 알아내는 것이 영리한 함수의 마지막 명령문입니다. 두 번째 매개변수 p는 중간 제품 값을 전달합니다.

 function N(x, p) { return x == 1 ? p : N(x - 1, p * x); }

이것은 위의 계승 함수를 작성하는 꼬리 재귀가 아닌 방법입니다(일부 C++ 컴파일러는 어쨌든 최적화할 수 있지만).

 function N(x) { return x == 1 ? 1 : x * N(x - 1); }

그러나 이것은 아닙니다:

 function F(x) { if (x == 1) return 0; if (x == 2) return 1; return F(x - 1) + F(x - 2); }

"꼬리 재귀 이해 – Visual Studio C++ – 어셈블리 보기 "라는 제목의 긴 게시물을 작성했습니다.

Community Wiki

꼬리 재귀 함수는 반환하기 전에 수행하는 마지막 작업이 재귀 함수 호출을 수행하는 재귀 함수입니다. 즉, 재귀 함수 호출의 반환 값이 즉시 반환됩니다. 예를 들어 코드는 다음과 같습니다.

 def recursiveFunction(some_params): # some code here return recursiveFunction(some_args) # no code after the return statement

꼬리 호출 최적화 또는 꼬리 호출 제거 를 구현하는 컴파일러와 인터프리터는 스택 오버플로를 방지하기 위해 재귀 코드를 최적화할 수 있습니다. 컴파일러 또는 인터프리터가 꼬리 호출 최적화(예: CPython 인터프리터)를 구현하지 않는 경우 이러한 방식으로 코드를 작성하면 추가적인 이점이 없습니다.

예를 들어 다음은 Python의 표준 재귀 계승 함수입니다.

 def factorial(number): if number == 1: # BASE CASE return 1 else: # RECURSIVE CASE # Note that `number *` happens *after* the recursive call. # This means that this is *not* tail call recursion. return number * factorial(number - 1)

그리고 이것은 계승 함수의 꼬리 호출 재귀 버전입니다.

 def factorial(number, accumulator=1): if number == 0: # BASE CASE return accumulator else: # RECURSIVE CASE # There's no code after the recursive call. # This is tail call recursion: return factorial(number - 1, number * accumulator) print(factorial(5))

(이것이 Python 코드이더라도 CPython 인터프리터는 꼬리 호출 최적화를 수행하지 않으므로 이와 같이 코드를 정렬하면 런타임 이점이 없습니다.)

계승 예제에 표시된 것처럼 꼬리 호출 최적화를 사용하려면 코드를 좀 더 읽기 어렵게 만들어야 할 수도 있습니다. (예를 들어 기본 케이스는 이제 약간 직관적이지 않으며 accumulator 매개변수는 일종의 전역 변수로 효과적으로 사용됩니다.)

그러나 꼬리 호출 최적화의 이점은 스택 오버플로 오류를 방지한다는 것입니다. (재귀 알고리즘 대신 반복 알고리즘을 사용하면 이와 동일한 이점을 얻을 수 있습니다.)

스택 오버플로는 호출 스택에 너무 많은 프레임 개체가 푸시되었을 때 발생합니다. 프레임 개체는 함수가 호출될 때 호출 스택에 푸시되고 함수가 반환될 때 호출 스택에서 꺼집니다. 프레임 객체에는 지역 변수 및 함수가 반환될 때 반환할 코드 행과 같은 정보가 포함됩니다.

재귀 함수가 반환하지 않고 재귀 호출을 너무 많이 수행하면 호출 스택이 프레임 개체 제한을 초과할 수 있습니다. (플랫폼에 따라 숫자가 다르며 Python에서는 기본적으로 1000개의 프레임 개체입니다.) 이로 인해 스택 오버플로 오류가 발생합니다. (여기서 이 웹사이트의 이름을 따온 것입니다!)

그러나 재귀 함수가 수행하는 마지막 작업이 재귀 호출을 수행하고 반환 값을 반환하는 것이라면 현재 프레임 개체를 호출 스택에 유지해야 할 이유가 없습니다. 결국 재귀 함수 호출 후 코드가 없으면 현재 프레임 개체의 로컬 변수에 매달릴 이유가 없습니다. 따라서 현재 프레임 개체를 호출 스택에 유지하는 대신 즉시 제거할 수 있습니다. 이것의 최종 결과는 호출 스택의 크기가 증가하지 않으므로 스택 오버플로가 발생하지 않는다는 것입니다.

컴파일러나 인터프리터는 꼬리 호출 최적화를 적용할 수 있는 시기를 인식할 수 있도록 꼬리 호출 최적화를 기능으로 가지고 있어야 합니다. 그럼에도 불구하고 꼬리 호출 최적화를 사용하기 위해 재귀 함수의 코드를 재정렬했을 수 있으며 이러한 잠재적인 가독성 감소가 최적화할 가치가 있는지 여부는 사용자에게 달려 있습니다.

Community Wiki

여기에 앞서 언급한 tailrecsum 함수의 Perl 5 버전이 있습니다.

 sub tail_rec_sum($;$){ my( $x,$running_total ) = (@_,0); return $running_total unless $x; @_ = ($x-1,$running_total+$x); goto &tail_rec_sum; # throw away current stack frame }

Brad Gilbert

이것은 꼬리 재귀에 대한 컴퓨터 프로그램의 구조와 해석 에서 발췌한 것입니다.

반복과 재귀를 대조하면서 재귀 프로세스의 개념과 재귀 절차의 개념을 혼동하지 않도록 주의해야 합니다. 프로시저를 재귀적이라고 설명할 때 프로시저 정의가 프로시저 자체를 (직접적으로든 간접적이든) 참조한다는 구문적 사실을 참조합니다. 그러나 선형 재귀와 같은 패턴을 따르는 프로세스를 설명할 때 프로시저가 작성되는 방식의 구문이 아니라 프로세스가 어떻게 진화하는지에 대해 말하는 것입니다. 팩트-이터(fact-iter)와 같은 재귀적 절차를 반복적인 프로세스를 생성하는 것으로 언급하는 것은 혼란스러워 보일 수 있습니다. 그러나 프로세스는 실제로 반복적입니다. 상태는 세 가지 상태 변수에 의해 완전히 캡처되며 인터프리터는 프로세스를 실행하기 위해 세 가지 변수만 추적하면 됩니다.

프로세스와 프로시저 사이의 구분이 혼란스러울 수 있는 한 가지 이유는 대부분의 공통 언어 구현(Ada, Pascal 및 C 포함)이 재귀 프로시저의 해석이 함께 증가하는 메모리 양을 소비하는 방식으로 설계되었기 때문입니다. 설명된 프로세스가 원칙적으로 반복적인 경우에도 프로시저 호출의 수입니다. 결과적으로 이러한 언어는 do, repeat, until, for 및 while과 같은 특수 목적의 "루핑 구문"에 의존해야만 반복 프로세스를 설명할 수 있습니다. Scheme의 구현은 이 결함을 공유하지 않습니다. 반복 프로세스가 재귀 프로시저로 설명되더라도 일정한 공간에서 반복 프로세스를 실행합니다. 이 속성을 사용하는 구현을 꼬리 재귀라고 합니다. 꼬리 재귀 구현을 사용하면 일반 프로시저 호출 메커니즘을 사용하여 반복을 표현할 수 있으므로 특수 반복 구문은 구문 설탕으로만 유용합니다.

Community Wiki

꼬리 재귀는 당신이 지금 살고 있는 삶입니다. "이전" 프레임으로 돌아갈 이유나 수단이 없기 때문에 동일한 스택 프레임을 계속해서 계속 재활용합니다. 과거는 끝났고 폐기될 수 있도록 끝났습니다. 프로세스가 불가피하게 죽을 때까지 한 프레임을 얻고 영원히 미래로 이동합니다.

_{일부 프로세스가 추가 프레임을 사용할 수 있지만 스택이 무한히 증가하지 않는 경우 꼬리 재귀로 간주된다는 점을 고려할 때 유추가 무너집니다.}

Community Wiki

꼬리 재귀는 함수가 재귀 호출의 반환 후에 계산이 수행되지 않는 함수의 끝("꼬리")에서 자신을 호출하는 재귀 함수입니다. 많은 컴파일러는 재귀 호출을 꼬리 재귀 또는 반복 호출로 변경하도록 최적화합니다.

숫자의 계승을 계산하는 문제를 고려하십시오.

간단한 접근 방식은 다음과 같습니다.

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

factorial(4)를 호출한다고 가정합니다. 재귀 트리는 다음과 같습니다.

 factorial(4) / \ 4 factorial(3) / \ 3 factorial(2) / \ 2 factorial(1) / \ 1 factorial(0) \ 1

위의 경우 최대 재귀 깊이는 O(n)입니다.

그러나 다음 예를 고려하십시오.

 factAux(m,n): if n==0 then m; else factAux(m*n,n-1); factTail(n): return factAux(1,n);

factTail(4)의 재귀 트리는 다음과 같습니다.

 factTail(4) | factAux(1,4) | factAux(4,3) | factAux(12,2) | factAux(24,1) | factAux(24,0) | 24

여기에서도 최대 재귀 깊이는 O(n)이지만 어떤 호출도 스택에 추가 변수를 추가하지 않습니다. 따라서 컴파일러는 스택을 제거할 수 있습니다.

Community Wiki

꼬리 재귀는 일반 재귀에 비해 꽤 빠릅니다. 조상 호출의 출력이 추적을 유지하기 위해 스택에 기록되지 않기 때문에 빠릅니다. 그러나 정상적인 재귀에서 모든 조상은 추적을 유지하기 위해 스택에 작성된 출력을 호출합니다.

Community Wiki

꼬리 호출 재귀와 꼬리 호출이 아닌 재귀 간의 몇 가지 핵심 차이점을 이해하기 위해 이러한 기술의 .NET 구현을 탐색할 수 있습니다.

다음은 C#, F# 및 C++\CLI의 몇 가지 예가 포함된 기사입니다. Adventures in Tail Recursion in C#, F# 및 C++\CLI .

C#은 꼬리 호출 재귀를 최적화하지 않지만 F#은 최적화합니다.

원리의 차이점은 루프 대 람다 미적분을 포함합니다. C#은 루프를 염두에 두고 설계되었지만 F#은 람다 미적분학의 원칙에서 구축되었습니다. 람다 미적분의 원리에 대한 아주 좋은(무료) 책은 Abelson, Sussman 및 Sussman의 Structure and Interpretation of Computer Programs를 참조하십시오.

F#의 꼬리 호출과 관련하여 아주 좋은 소개 문서 는 F#의 꼬리 호출에 대한 자세한 소개를 참조하세요. 마지막으로 꼬리가 아닌 재귀와 꼬리 호출 재귀(F#)의 차이점을 다루는 기사가 있습니다. 꼬리 재귀와 F 샤프의 꼬리가 아닌 재귀 .

C#과 F# 사이의 꼬리 호출 재귀의 설계 차이점에 대해 알아보려면 C# 및 F#에서 꼬리 호출 연산 코드 생성을 참조하세요.

C# 컴파일러가 꼬리 호출 최적화를 수행하지 못하게 하는 조건을 알고 싶다면 JIT CLR 꼬리 호출 조건 문서를 참조하십시오.

Community Wiki

재귀는 자신을 호출하는 함수를 의미합니다. 예를 들어:

 (define (un-ended name) (un-ended 'me) (print "How can I get here?"))

꼬리 재귀는 함수를 종료하는 재귀를 의미합니다.

 (define (un-ended name) (print "hello") (un-ended 'me))

끝이 없는 함수(프로시저, Scheme 전문 용어)가 하는 마지막 일은 자신을 호출하는 것입니다. 또 다른 (더 유용한) 예는 다음과 같습니다.

 (define (map lst op) (define (helper done left) (if (nil? left) done (helper (cons (op (car left)) done) (cdr left)))) (reverse (helper '() lst)))

도우미 프로시저에서 왼쪽이 nil이 아닌 경우 마지막으로 하는 일은 자신을 호출하는 것입니다. 이것은 기본적으로 목록을 매핑하는 방법입니다.

꼬리 재귀는 인터프리터(또는 언어 및 공급업체에 따라 다름)가 이를 최적화하고 while 루프와 동등한 것으로 변환할 수 있다는 큰 이점이 있습니다. 사실, Scheme 전통에서 대부분의 "for" 및 "while" 루프는 꼬리 재귀 방식으로 수행됩니다(내가 아는 한 for 및 while은 없습니다).

magice

재귀에는 머리 재귀 와 꼬리 재귀 의 두 가지 기본 유형이 있습니다.

헤드 재귀 에서 함수는 재귀 호출을 수행한 다음 재귀 호출의 결과를 사용하여 더 많은 계산을 수행합니다.

꼬리 재귀 함수에서 모든 계산이 먼저 발생하고 재귀 호출이 마지막으로 발생합니다.

이 슈퍼 멋진 게시물에서 가져 왔습니다. 읽어보시기 바랍니다.

Community Wiki

이 질문에는 훌륭한 답변이 많이 있습니다. 하지만 "꼬리 재귀" 또는 최소한 "적절한 꼬리 재귀"를 정의하는 방법에 대한 대안을 제시하지 않을 수 없습니다. 즉, 프로그램에서 특정 표현식의 속성으로 보아야 합니까? 아니면 프로그래밍 언어 구현의 속성으로 보아야 합니까?

후자의 관점에 대한 자세한 내용은 Will Clinger의 "적절한 꼬리 재귀 및 공간 효율성"(PLDI 1998)의 고전 논문 에서 "적절한 꼬리 재귀"를 프로그래밍 언어 구현의 속성으로 정의했습니다. 정의는 구현 세부 사항(예: 호출 스택이 실제로 런타임 스택을 통해 표시되는지 또는 프레임의 힙 할당 연결 목록을 통해 표시되는지 여부)을 무시할 수 있도록 구성됩니다.

이를 수행하기 위해 일반적으로 보는 프로그램 실행 시간이 아니라 프로그램 공간 사용량에 대한 점근적 분석을 사용합니다. 이렇게 하면 힙 할당 연결 목록과 런타임 호출 스택의 공간 사용량이 점근적으로 동일하게 됩니다. 따라서 프로그래밍 언어 구현 세부 사항을 무시하게 됩니다(실제로는 확실히 중요한 세부 사항이지만 주어진 구현이 "속성 꼬리 재귀" 요구 사항을 충족하는지 여부를 결정하려고 할 때 물을 꽤 혼란스럽게 할 수 있습니다. )

이 논문은 여러 가지 이유로 주의 깊게 연구할 가치가 있습니다.

• 프로그램의 꼬리 표현 과 꼬리 호출 에 대한 귀납적 정의를 제공합니다. (이러한 정의와 그러한 호출이 중요한 이유는 여기에 제공된 대부분의 다른 답변의 주제인 것 같습니다.)

  다음은 텍스트의 풍미를 제공하기 위한 정의입니다.

  정의 1 Core Scheme으로 작성된 프로그램의 꼬리 표현 은 다음과 같이 귀납적으로 정의된다.

  1. 람다 식의 본문은 꼬리 식입니다.
  2. (if E0 E1 E2) 가 꼬리 표현식이면 E1 과 E2 는 모두 꼬리 표현식입니다.
  3. 다른 것은 꼬리 표현이 아닙니다.

  정의 2 꼬리 호출 은 프로시저 호출인 꼬리 표현식입니다.

(꼬리 재귀 호출, 또는 논문에서 말했듯이 "자체 꼬리 호출"은 프로시저가 자체적으로 호출되는 꼬리 호출의 특별한 경우입니다.)

• Core Scheme을 평가하기 위한 6개의 다른 "기계"에 대한 형식적 정의를 제공합니다. 여기서 각 기계는 각각이 속한 점근적 공간 복잡도 클래스를 제외하고 동일한 관찰 가능한 동작을 가집니다.

  예를 들어, 각각 1. 스택 기반 메모리 관리, 2. 가비지 수집, 테일 호출 없음, 3. 가비지 수집 및 테일 호출이 있는 시스템에 대한 정의를 제공한 후, 이 문서는 다음과 같은 훨씬 더 고급 스토리지 관리 전략으로 계속 진행됩니다. 4. 환경 5. 그 폐쇄의 바로 자유 변수에 폐쇄 환경을 줄이고, 꼬리 호출의 마지막 하위 식 인수의 평가를 통해 보존 할 필요가 없다 "evlis 꼬리 재귀", 및 6. Appel과 Shao가 정의한 소위 "safe-for-space" 의미론.

• 기계가 실제로 6개의 별개의 공간 복잡도 클래스에 속한다는 것을 증명하기 위해, 논문은 비교 중인 각 기계 쌍에 대해 한 기계에서는 점근적 공간 폭증을 노출하지만 다른 기계에서는 노출하지 않는 프로그램의 구체적인 예를 제공합니다.

---

(지금 내 답변을 읽으면서 Clinger 논문 의 중요한 요점을 실제로 포착했는지 확실하지 않습니다. 그러나 안타깝게도 지금은 이 답변을 개발하는 데 더 많은 시간을 할애할 수 없습니다.)

Community Wiki

각 재귀 케이스가 다른 인수를 사용하여 함수 자체에 대한 호출 로만 구성되는 경우 함수는 꼬리 재귀입니다. 또는 꼬리 재귀는 보류 중인 작업이 없는 재귀입니다 . 이것은 프로그래밍 언어에 독립적인 개념입니다.

다음과 같이 정의된 함수를 고려하십시오.

 g(a, b, n) = a * b^n

가능한 꼬리 재귀 공식은 다음과 같습니다.

 g(a, b, n) | n is zero = a | n is odd = g(a*b, b, n-1) | otherwise = g(a, b*b, n/2)

당신은 각각의 RHS 살펴보면 g(...) 재귀 경우를 포함, 당신은 RHS의 몸 전체를 호출하는 것을 확인할 수 있습니다 g(...) , 단지 그. 이 정의는 꼬리 재귀 입니다.

비교를 위해 비꼬리 재귀 공식은 다음과 같을 수 있습니다.

 g'(a, b, n) = a * f(b, n) f(b, n) | n is zero = 1 | n is odd = f(b, n-1) * b | otherwise = f(b, n/2) ^ 2

f(...) 각 재귀 사례에는 재귀 호출 후에 발생해야 하는 보류 중인 작업이 있습니다.

우리가에서 갔을 때주의 g' 에 g , 우리는 곱셈의 연관성 (및 교환 법칙)의 필수 사용했다. 이것은 우연이 아니며 재귀를 꼬리 재귀로 변환해야 하는 대부분의 경우 이러한 속성을 사용할 것입니다. 보류 상태로 두지 않고 일부 작업을 열성적으로 수행하려면 연관성과 같은 것을 사용하여 증명해야 합니다. 답은 같을 것이라는 것입니다.

꼬리 재귀 호출은 일반 재귀 호출에 스택을 사용하는 것과 달리 역방향 점프로 구현할 수 있습니다. 꼬리 호출을 감지하거나 뒤로 점프하는 것은 일반적으로 간단합니다. 그러나 뒤로 점프가 가능하도록 인수를 재정렬하는 것이 종종 어렵습니다. 이 최적화는 무료가 아니므로 언어 구현은 이 최적화를 구현하지 않거나 'tailcall' 명령으로 재귀 호출을 표시하거나 더 높은 최적화 설정을 선택하여 옵트인을 요구할 수 있습니다.

그러나 일부 언어(예: Scheme)는 꼬리 재귀 함수를 최적화하기 위해 모든 구현을 요구합니다. 심지어 꼬리 위치의 모든 호출도 가능합니다.

역방향 점프는 일반적으로 대부분의 명령형 언어에서 (while) 루프로 추상화되며, 역방향 점프에 최적화된 꼬리 재귀는 루프와 동형입니다.

Community Wiki

많은 사람들이 이미 여기에서 재귀에 대해 설명했습니다. Riccardo Terrell의 "Concurrency in .NET, Modern Patterns of Concurrent and Parallel programming" 책에서 재귀가 제공하는 몇 가지 이점에 대한 몇 가지 생각을 인용하고 싶습니다.

“함수 재귀는 상태 돌연변이를 피하기 때문에 FP에서 반복하는 자연스러운 방법입니다. 각 반복 동안 새 값이 루프 생성자에 전달되어 업데이트(변경)됩니다. 또한 재귀 함수를 구성하여 프로그램을 보다 모듈화하고 병렬화를 활용할 수 있는 기회를 제공할 수 있습니다."

다음은 꼬리 재귀에 대한 같은 책의 몇 가지 흥미로운 참고 사항입니다.

Tail-call 재귀는 일반 재귀 함수를 위험과 부작용 없이 큰 입력을 처리할 수 있는 최적화된 버전으로 변환하는 기술입니다.

참고 최적화로 꼬리 호출을 하는 주된 이유는 데이터 지역성, 메모리 사용 및 캐시 사용을 개선하기 위한 것입니다. 꼬리 호출을 수행함으로써 수신자는 호출자와 동일한 스택 공간을 사용합니다. 이것은 메모리 압력을 줄입니다. 동일한 메모리가 후속 호출자에 대해 재사용되고 새 캐시 라인을 위한 공간을 만들기 위해 이전 캐시 라인을 제거하는 대신 캐시에 머물 수 있기 때문에 캐시가 약간 향상됩니다.

Community Wiki

함수의 마지막 작업이 재귀 호출인 특수한 형태의 재귀입니다. 재귀는 현재 스택 프레임에서 호출을 실행하고 새 스택 프레임을 만드는 대신 결과를 반환하여 최적화될 수 있습니다.

재귀 호출이 함수에 의해 마지막으로 실행되는 경우 재귀 함수는 꼬리 재귀입니다. 예를 들어 다음 C++ 함수 print()는 꼬리 재귀입니다.

꼬리 재귀 함수의 예

 void print(int n) { if (n < 0) return; cout << " " << n; print(n-1);} // The last executed statement is recursive call

꼬리 재귀는 컴파일러에 의해 최적화될 수 있으므로 꼬리 재귀 함수가 아닌 꼬리 재귀 함수보다 낫다고 생각되는 꼬리 재귀 함수. 컴파일러가 꼬리 재귀 함수를 최적화하는 데 사용하는 아이디어는 단순합니다. 재귀 호출이 마지막 명령문이기 때문에 현재 함수에서 할 일이 없기 때문에 현재 함수의 스택 프레임을 저장하는 것은 아무 소용이 없기 때문입니다.

Community Wiki

출처 : http:www.stackoverflow.com/questions/33923/what-is-tail-recursion