꼬리 재귀 스택 오버플로

Question

필자가 아는 한 꼬리 재귀 함수는 return 문과 같은 마지막 단계에서 스스로를 호출하지만 모든 다른 인스턴스도 종료 될 때까지 함수의 첫 번째 인스턴스는 종료되지 않습니다 따라서 여러 인스턴스에 도달하면 스택 오버플로가 발생합니다. 재귀가 마지막 단계에 있다는 것을 감안할 때, 다음 인스턴스 이전 또는 직전에 이전 인스턴스를 종료 할 수있는 방법이 있습니까? 인스턴스의 유일한 목적이 다음 인스턴스를 호출하는 것이라면 그것이 메모리에 있어야하는 이유는 없습니다.

Answer 1

예, 일부 컴파일러는 꼬리 재귀를 최적화하여 추가 스택 공간이 필요하지 않도록합니다. 예를 들어이 C 함수 예제를 보겠습니다.

int braindeadrecursion(int n) 
{ 
    if (n == 0) 
    return 1; 

    return braindeadrecursion(n - 1); 
} 

이 함수는 매우 쉽습니다. 당신이 볼 수 있듯이, 재귀 호출이 값 0x24 거기에

_braindeadrecursion: 
00 pushq %rbp 
01 movq %rsp,%rbp 
04 subq $0x10,%rsp 
08 movl %edi,0xf8(%rbp) 
0b movl 0xf8(%rbp),%eax 
0e cmpl $_braindeadrecursion,%eax 
11 jne 0x0000001c 
13 movl $0x00000001,0xfc(%rbp) 
1a jmp 0x0000002e 
1c movl 0xf8(%rbp),%eax 
1f subl $0x01,%eax 
22 movl %eax,%edi 
24 callq _braindeadrecursion 
29 movl %eax,%ecx 
2b movl %ecx,0xfc(%rbp) 
2e movl 0xfc(%rbp),%eax 
31 addq $0x10,%rsp 
35 popq %rbp 
36 ret 

: 그냥 그 소리는 다음과 같습니다 내 컴퓨터에서 코드를 생성, 최적화하지 않으면 1을 반환합니다. 더 높은 최적화를 시도해 보겠습니다.

_braindeadrecursion: 
00 pushq %rbp 
01 movq %rsp,%rbp 
04 movl $0x00000001,%eax 
09 popq %rbp 
0a ret 

자, 이제 더 이상 재귀를 보지 마십시오! 이 예제는 매우 단순하지만 더 복잡한 꼬리 재귀 케이스에서 여전히 최적화가 발생할 수 있습니다.

Answer 2

- 스택 크기를 늘리거나 - 반복을 사용하지 않고 대신 일종의 반복을 사용합니다.