예, 일부 언어 및 컴파일러는 재귀 논리를 비 재귀 논리로 변환합니다. 이것을 테일 콜 최적화라고합니다. 모든 재귀 호출이 테일 콜에 최적화되는 것은 아닙니다. 이 상황에서 컴파일러는 다음 형식의 기능을 인식합니다.

int foo(n) {
  ...
  return bar(n);
}

여기서 언어는 반환되는 결과가 다른 함수의 결과임을 인식하고 새 스택 프레임이있는 함수 호출을 점프로 변경합니다.

고전적인 계승 방법을 실현하십시오.

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

반품시 필요한 검사로 인해 테일 콜 최적화 가 불가능 합니다.

이 테일 콜을 최적화하려면

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

이 코드를 컴파일하면 gcc -O2 -S fact.c(컴파일러에서 최적화를 활성화하려면 -O2가 필요하지만, -O3의 최적화가 많으면 사람이 읽기가 어렵습니다 …)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

하나는 (새로운 스택 프레임으로 서브 루틴 호출을 수행함) 보다는 segment .L4에서 볼 수 있습니다 .jnecall

이것은 C로 수행되었다는 점에 유의하십시오. java의 tail call 최적화는 어렵고 JVM 구현에 따라 다릅니다. tail-recursion + java 및 tail-recursion + 최적화 는 찾아보기에 좋은 태그 세트입니다. 다른 JVM 언어는 꼬리 재귀를 더 잘 최적화 할 수 있습니다 (클로저 시도 ( 꼬리 호출 최적화 를 요구하는 반복 ) 또는 스칼라).

답변