재귀 함수, 스택 오버플로 및 Y 결합 자

Question

약 8 억 번 호출해야하는 재귀 함수 (C#의 경우)가 있습니다. 이것은 분명히 일반적으로 약 900 번째 호출 후에 스택 오버 플로우를 발생시킵니다. 이 루프를 여러 개의 루프로 쫓아 냈지만 재귀 패턴은 훨씬 쉽고 유지 보수가 간편합니다.

저는 y-combinator를 사용하여 재귀 함수를 구현하는 방법을 살펴보고 있습니다. 스택 결합 오버플로 문제를 해결하고 다중 중첩 루프를 해결해야한다는 것을 알고 있습니다.

누구나 y-combinator를 사용해 본 경험이 있습니까? 스택 오버플로가 계속 붙어 있을까요?

계승의 간단한 예를 들어보십시오. 5,000보다 큰 숫자의 계승 (factorialial)은 스택 오버플로를 유발합니다. 그 시나리오에서 y-combinator를 올바르게 사용했다면 스택 오버플로를 수정하겠습니까?

구현하기가 쉽지 않으므로 y 조합자를 구현하고 학습하는 개발 노력/리소스를 사용하기 전에이를 확인하고 싶습니다.

Answer 1

아니요, Y- 결합기를 사용하면 도움이되지 않습니다. 8 억 번을해야한다면, (a) 반복하거나, (b) 루프 (또는 귀하의 기능에 8 억 건의 호출을 작성한다고 가정)을 할 수 있습니다. Y-combinator는 반복하지 않기 때문에 반복되어야합니다.

적절한 꼬리 재귀 (예 : 스키마)를 제공하는 런타임 환경을 사용하지 않는 한 루프가 필요합니다.

당신이 선택한 언어로 처음부터 Y- 연결자를 구현하는 것은 훌륭한 운동입니다.

Answer 2

Y 결합자가 유용하지만 제 생각에는 꼬리 재귀 함수에 대한 스택 사용을 제거하는 꼬리 재귀 최적화이 정말로 필요합니다. 꼬리 재귀 호출은 인 경우에만 가능하며 모든 재귀 호출의 결과는 호출자에 의해 즉시 반환되며 호출 후 추가 계산이 수행되지 않습니다. 불행히도 C#은 꼬리 재귀 최적화를 지원하지 않지만 트램 폴린으로 꼬리 재귀 메서드에서 트램 폴린 래핑 된 메서드로 쉽게 변환 할 수 있습니다. 반응성 확장에 사용되는

는

// Tail 
int factorial(int n) { return factorialTail(n, 1, 1); } 
int factorialTail(int n, int i, int acc) { 
    if (n < i) return acc; 
    else return factorialTail(n, i + 1, acc * i); 
} 

// Trampoline 
int factorialTramp(int n) { 
    var bounce = new Tuple<bool,int,int>(true,1,1); 
    while(bounce.Item1) bounce = factorialOline(n, bounce.Item2, bounce.Item3); 
    return bounce.Item3; 
} 
Tuple<bool,int,int> factorialOline(int n, int i, int acc) { 
    if (n < i) return new Tuple<bool,int,int>(false,i,acc); 
    else return new Tuple<bool,int,int>(true,i + 1,acc * i); 
} 

는

Answer 3

당신은 트램 폴린을 사용할 수 있습니다, 나는 http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

하나의 솔루션은 루프를 사용하도록 기능 (들)을 변환하는 것입니다 내 블로그에 그것을 설명하기 위해 노력하고 명시 적 있다 문맥 데이터 구조. 컨텍스트는 사람들이 일반적으로 호출 스택이라고 생각하는 것을 나타냅니다. my answer to another question about converting to tail recursion이 유용 할 수 있습니다. 관련 단계는 1에서 5까지입니다. 6과 7은 특정 기능에 특화된 반면에, 당신은 더 복잡한 것처럼 들립니다.

"쉬운"대안은 각 기능에 깊이 카운터를 추가하는 것입니다. (실험에 의해 결정된) 약간의 한계를 치면 새로운 스택으로 재귀를 계속하기 위해 새로운 스레드를 생성합니다. 이전 스레드는 새 스레드가 결과를 보내길 기다리는 것을 차단합니다 (또는 재밌게하려면 결과 또는 예외를 다시 발생시키는 것이 좋습니다). 깊이 카운터는 새 스레드의 경우 0으로 되돌아갑니다. 한계에 도달하면 세 번째 스레드를 만드는 등의 작업을 수행합니다. 쓰레드 생성 비용을 필요 이상으로 지불하는 것을 피하기 위해 쓰레드를 캐시한다면, 프로그램을 대대적으로 재구성하지 않고도 수용 가능한 성능을 얻을 수 있기를 바랍니다.