•  03-07-2019
  •  | 
  •  

문제

stackoverflows를 피하는 방법에 대한 재귀를 사용할 때 일반적인 규칙이 있습니까?

도움이 되었습니까?

해결책

재발 할 수있는 횟수는 다음에 따라 다릅니다.

  • 스택 크기 (일반적으로 1MB IIRC이지만 이진은 손으로 편집 할 수 있습니다. 그렇게하지는 않을 것입니다)
  • 재귀 사용의 각 레벨을 얼마나 많이 스택하는지 (10 개의 캡처 된 방법 Guid 로컬 변수는 로컬 변수가없는 메소드보다 더 많은 스택을 취합니다.
  • 당신이 사용하고있는 JIT- 때때로 JIT ~ 할 것이다 꼬리 재귀를 사용하십시오. 다른 경우에는 그렇지 않습니다. 규칙은 복잡하고 기억할 수 없습니다. (거기에 David Broman의 블로그 게시물은 2007 년부터 돌아 왔습니다, 그리고 동일한 저자/날짜의 MSDN 페이지, 그러나 그들은 지금까지 구식일지도 모릅니다.)

스택 오버 플로우를 피하는 방법? 너무 멀리 되돌아 보지 마십시오. :) 당신이 당신의 재귀가 아주 멀리 가지 않고 종료 될 것이라고 합리적으로 확신 할 수 없다면 (나는 매우 안전하지만 "10 이상"에 대해 걱정할 것입니다) 재귀를 피하기 위해 그것을 다시 작성하십시오.

다른 팁

실제로 사용중인 재귀 알고리즘에 달려 있습니다. 간단한 재귀라면 다음과 같은 일을 할 수 있습니다.

public int CalculateSomethingRecursively(int someNumber)
{
    return doSomethingRecursively(someNumber, 0);
}

private int doSomethingRecursively(int someNumber, int level)
{
    if (level >= MAX_LEVEL || !shouldKeepCalculating(someNumber))
        return someNumber;
    return doSomethingRecursively(someNumber, level + 1);
}

이 접근법은 재귀 수준이 논리적 한계로 정의 될 수있는 경우에만 유용하다는 점은 주목할 가치가 있습니다. 이런 일이 발생할 수없는 경우 (예 : 분할 및 정복 알고리즘), 단순성 대 성능과 리소스 제한의 균형을 맞추는 방법을 결정해야합니다. 이 경우, Arbritary 사전 정의 된 한계에 부딪히면 방법을 전환해야 할 수도 있습니다. QuickSort 알고리즘에서 사용한 효과적인 수단은 목록의 총 크기의 비율로 수행하는 것입니다. 이 경우 논리적 한계는 조건이 더 이상 최적이 아닌 경우의 결과입니다.

나는 아무것도 모른다 하드 세트 stackoverflows를 피하기 위해. 나는 개인적으로 보장하려고 노력합니다.
1. 기본 사례가 제대로 있습니다.
2. 코드는 어느 시점에서 기본 케이스에 도달합니다.

많은 스택 프레임을 생성하고 있다면 재귀를 루프로 풀어주는 것을 고려할 수 있습니다.

특히 여러 수준의 재귀를하는 경우 (A-> B-> C-> A-> B ...) 해당 레벨 중 하나를 루프로 추출하여 메모리를 절약 할 수 있습니다.

연속 통화 사이의 스택에 많이 남지 않으면 정상 한계는 약 15000-25000 레벨의 깊이입니다. IIS 6+에있는 경우 25%.

대부분의 재귀 조류는 반복적으로 표현 될 수 있습니다.

할당 된 스택 공간을 늘리는 다양한 방법이 있지만 반복 버전을 먼저 찾을 수 있습니다. :)

합리적인 스택 크기를 갖고 문제를 나누고 문제를 정복하여 실제로가 아니라 작은 문제를 지속적으로 작업 할 수 있도록하는 것 외에.

방금 꼬리 추방에 대해 생각했지만 C#이 그것을 지원하지 않는다는 것이 밝혀졌습니다. 그러나 .net-framework가이를 지원하는 것 같습니다.

http://blogs.msdn.com/abhinaba/archive/2007/07/27/tail-recursion-on-net.aspx

스레드의 기본 스택 크기는 기본 CLR에서 실행중인 경우 1MB입니다. 그러나 다른 호스트는이를 변경할 수 있습니다. 예를 들어 ASP 호스트는 기본값을 256 KB로 변경합니다. 즉, VS에서 완벽하게 실행되는 코드가있을 수 있지만 실제 호스팅 환경에 배치하면 중단됩니다.

다행히 올바른 생성자를 사용하여 새 스레드를 만들 때 스택 크기를 지정할 수 있습니다. 내 경험상 그것은 거의 필요하지 않지만, 이것이 해결책 인 경우를 보았습니다.

이진 자체의 PE 헤더를 편집하여 기본 크기를 변경할 수 있습니다. 메인 스레드의 크기를 변경하려는 경우 유용합니다. 그렇지 않으면 스레드를 만들 때 적절한 생성자를 사용하는 것이 좋습니다.

나는 이것에 대한 짧은 기사를 썼다 여기. 기본적으로, 나는 깊이있는 옵션 매개 변수를 전달하고, 더 깊이 갈 때마다 1을 추가합니다. 재귀 방법 내에서 나는 값의 깊이를 점검합니다. 그것이 설정 한 값보다 크면 예외를 던집니다. 값 (임계 값)은 응용 프로그램 요구에 따라 다릅니다.

시스템 제한에 대해 물어봐야한다면 아마도 끔찍한 일을하고있을 것입니다.

따라서 정상 작동에서 스택 오버플로를 얻을 수 있다고 생각되면 문제에 대한 다른 접근 방식을 생각해야합니다.

특히 C#에 Generic :: Stack Collection이 있기 때문에 재귀 기능을 반복적 인 기능으로 변환하는 것은 어렵지 않습니다. 스택 유형을 사용하면 스택 대신 프로그램의 힙으로 사용 된 메모리를 움직입니다. 이렇게하면 재귀 데이터를 저장할 수있는 전체 주소 범위가 제공됩니다. 충분하지 않으면 데이터를 디스크로 페이지에 페이지를 페이지에 페이지를 표시하는 것은 그리 어렵지 않습니다. 그러나이 단계에 도달하면 다른 솔루션을 진지하게 고려합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top