C++ 컴파일 오류: 너무 깊은 재귀로 인해 스택 오버플로가 발생합니다. 어떻게 해결합니까?

C++는 널리 사용되는 프로그래밍 언어이므로 컴파일 및 실행 중에 다양한 오류가 발생할 수 있습니다. 일반적인 실수 중 하나는 너무 깊게 재귀하여 스택 오버플로를 일으키는 것입니다.

재귀에서 재귀 수준이 너무 많으면 프로그램에 스택 오버플로 오류가 발생합니다. 이는 재귀 함수가 각 재귀 중에 로컬 변수와 함수 호출을 저장하기 위해 일정량의 메모리 공간이 필요하기 때문입니다. 각 재귀는 이러한 로컬 변수와 함수 호출을 함수 호출 스택으로 푸시합니다. 스택 크기가 제한됩니다. 이 제한을 초과하면 스택 오버플로가 발생하여 프로그램이 중단됩니다.

그렇다면 너무 깊은 재귀로 인한 스택 오버플로를 어떻게 해결해야 할까요? 다음은 몇 가지 솔루션입니다.

1. 재귀를 루프로 다시 작성

재귀 함수의 본질은 역추적을 포함하는 루프이므로 프로그램 논리에 영향을 주지 않고 재귀 함수를 루프로 다시 작성할 수 있습니다. 이를 통해 재귀로 인한 오버헤드를 줄여 스택 오버플로 위험을 줄일 수 있습니다.

예를 들어, 다음은 피보나치 수열을 계산하는 재귀 함수입니다.

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

이를 다음 루프 형식으로 다시 작성할 수 있습니다.

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

2. 스택 공간 늘리기

크기를 설정하여 이를 방지할 수 있습니다. 스택 공간 스택 오버플로. Windows에서는 프로그램 실행 파일의 스택 공간 크기를 수정하여 이를 달성할 수 있으며, Linux에서는 ulimit 명령을 사용하여 스택 크기를 제어할 수 있습니다. 이 접근 방식에서 주의할 점은 스택 공간이 너무 많으면 시스템 리소스를 차지하므로 장단점을 잘 따져봐야 한다는 것입니다.

3. 재귀 알고리즘 조정

때때로 재귀 알고리즘 자체에 문제가 있어 재귀 수준이 너무 높아질 수 있습니다. 이 경우 재귀 알고리즘을 최적화하고 재귀 호출 수를 줄여 스택 오버플로 위험을 줄여야 합니다.

예를 들어 다음은 피보나치 수열을 풀기 위한 재귀 알고리즘입니다.

int fib(int n) {
    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

재귀 호출 횟수를 줄이기 위해 메모 검색을 통해 이 알고리즘을 최적화할 수 있습니다.

int fib(int n, unordered_map<int, int>& memo) {
    if (n == 0 || n == 1) {
        return n;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = fib(n - 1, memo) + fib(n - 2, memo);
    memo[n] = ans;
    return ans;
}

int fib(int n) {
    unordered_map<int, int> memo;
    return fib(n, memo);
}

4. 재귀 함수의 반복 계산을 피하세요

In 재귀 함수에는 반복 계산의 하위 문제가 있을 수 있습니다. 재귀 호출 수를 줄이기 위해 캐싱 메커니즘을 사용하면 이를 방지할 수 있습니다.

예를 들어 카탈로니아 숫자를 계산해야 하는 경우 캐싱 메커니즘을 사용하여 반복 계산을 피할 수 있습니다.

int catalan(int n, unordered_map<int, int>& memo) {
    if (n <= 1) {
        return 1;
    }
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += catalan(i, memo) * catalan(n - 1 - i, memo);
    }
    memo[n] = ans;
    return ans;
}

int catalan(int n) {
    unordered_map<int, int> memo;
    return catalan(n, memo);
}

간단히 말해서 너무 깊은 재귀로 인해 발생하는 스택 오버플로를 방지하는 방법은 여러 가지가 있으며 다음 중 하나를 선택해야 합니다. 구체적인 상황에 따라 적절한 방법. 재귀 함수를 작성할 때 재귀의 깊이에 주의하고 프로그램이 올바르게 실행되는지 충분히 테스트하십시오.

위 내용은 C++ 컴파일 오류: 너무 깊은 재귀로 인해 스택 오버플로가 발생합니다. 어떻게 해결합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!