재귀 호출을 사용하지 않고 재귀 함수 다시 쓰기

Question

재귀 호출을 쉽게 구현하거나 원치 않는 설정에서 기존 코드를 다시 작성합니다. (그리고 Fortran 77에서 알아야 할 필요가있다.) 나는 처음부터 스택을 만들어서 필요한 호출을 추적하는 방법에 대해 생각해 보았다. 그러나 이것은 kludgy처럼 보였고, 배열에 메모리를 할당하지는 않았다. 재귀가 깊지 않습니다. (Fortran 77이 동적 배열 크기 조정을 지원하지 않는다고 확신하지 못합니다.) 분명히 재귀 함수를 사용하여 스택에 공간을 낭비하지 않으면 서 재귀 적으로 재 작성하는 방법에 대한 일반적인 해결책에 대한 다른 제안 사항은 무엇입니까?

많은 감사, 옛 문화 체육 관광부

Answer 1

코드가 꼬리 재귀 (즉, 함수가 직접 다른 처리없이 모든 재귀 호출의 결과를 반환한다) 다음은 스택없이 명령 적 기능을 재 작성하는 것이 가능 사용하는 경우 :

function dosomething(a,b,c,d) 
{ 
    // manipulate a,b,c,d 
    if (condition) 
    return dosomething(a,b,c,d) 
    else 
    return something; 
} 

속으로 :

function dosomething(a,b,c,d) 
{ 
    while (true) 
    { 
    // manipulate a,b,c,d 
    if (condition) continue; 
    else return something; 
    } 
} 

꼬리 재귀가 없으면 스택 (또는 유사한 중간 저장 장치)을 사용하는 것이 유일한 해결책입니다.

function fib(n) 
{ 
    // valid for n >= 0 
    if (n < 2) 
     return n; 
    else 
     return fib(n-1) + fib(n-2); 
} 

그러나 메모이 제이션없이 걸리는 O (EXP^N) O와 연산 (N) 스택 공간 : 루프로 쓸 수

Answer 2

대부분의 재귀 함수는 쉽게 공간 낭비에 관해서는, 루프로 다시 작성할 수 있습니다 - 재귀 많은 (전부는 아니지만) 알고리즘이 실제로 그런 종류의에 의존하기 때문에, 기능에 따라 달라집니다 저장소 (그러나 루프 버전은 일반적으로이 경우에도 더 효율적입니다).

Answer 3

고전 재귀 함수는 피보나치 함수이다.

은 그것은 다시 작성할 수 있습니다 :

function fib(n) 
{ 
    if (n < 2) 
     return n; 
    var a = 0, b = 1; 
    while (n > 1) 
    { 
     var tmp = a; 
     a = b; 
     b = b + tmp; 
     n = n - 1; 
    } 
    return b; 
} 

하지만이 기능은 자동 프로세스에 일반화 될 수 있는지 확실하지 않습니다, 어떻게 작동하는지에 대한 지식을 포함한다.