태그 보관물: recursion

recursion

컴파일러가 재귀 논리를 동등한 비 재귀 논리로 변환 할 수 있습니까? #을 프로그래밍 할

F #을 배우고 있으며 C #을 프로그래밍 할 때 어떻게 생각하는지에 영향을주기 시작했습니다. 이를 위해 결과가 가독성을 향상시키고 스택 오버플로로 감기는 것을 생각할 수 없을 때 재귀를 사용하고 있습니다.

이것은 컴파일러가 재귀 함수를 동등한 비 재귀 형식으로 자동 변환 할 수 있는지 묻습니다.

답변

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

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 언어는 꼬리 재귀를 더 잘 최적화 할 수 있습니다 (클로저 시도 ( 꼬리 호출 최적화 를 요구하는 반복 ) 또는 스칼라).

답변

조심스럽게 밟으십시오.

대답은 ‘그렇지만’은 아니지만 항상 그런 것은 아닙니다. 이것은 몇 가지 다른 이름을 사용하는 기술이지만 여기 와 wikipedia 에서 꽤 확실한 정보를 찾을 수 있습니다 .

나는 “Tail Call Optimization”이라는 이름을 선호하지만 다른 사람들도 있고 어떤 사람들은이 용어를 혼동 할 것입니다.

그것은 깨달아야 할 몇 가지 중요한 것들이 있다고 말했습니다.

  • 테일 호출을 최적화하려면 테일 호출에는 호출시 알려진 매개 변수가 필요합니다. 매개 변수 중 하나는 자체 기능에 대한 호출을 의미하는 경우, 이는 그 수 이 컴파일시에 확장 할 수없는 상기 루프의 임의의 중첩을 필요로하기 때문에, 루프로 전환 될 수있다.

  • C #은 테일 호출을 안정적으로 최적화 하지 않습니다 . IL에는 F # 컴파일러가 방출하도록 지시가 있지만 C # 컴파일러는 일관성이 없어야하며 JIT 상황에 따라 JIT가 전혀 수행하지 않을 수도 있습니다. 모든 표시는 C #에서 최적화 된 테일 호출에 의존해서는 안되며 그렇게 할 때 오버플로의 위험은 심각하고 실제적입니다

답변