为什么我的递归代码导致堆栈溢出错误？

Question

此代码在“算法简介”一书中给出。为此，我使用1个索引数组

#include <cstdlib> 
#include <iostream> 

using namespace std; 
int n=6; 
int x[1000]; 

void max_heapify(int a[],int i) 
{ 
    int left=2*i; 
    int right=2*i+1; 
    int largest=i; 
    if(left<=n && a[left]>a[largest]){ 
     largest=left; 

    } 
    if(right<=n && a[right]>a[largest]) 
    { 
     largest=right; 

    } 
    if(largest!=i) 
    { 
     int t=a[i]; 
     a[i]=a[largest]; 
     a[largest]=t; 

    } 
    max_heapify(a,largest); 
} 
void max_heap(int a[]) 
{ 
    int heap_length=n; 
    for(int i=n/2;i>=1;i--) 
     max_heapify(a,i); 

} 
int main(int argc, char *argv[]) 
{ 
    for(int i=1;i<=n;i++) 
     cin>>x[i]; 
    max_heap(x); 
    cout<<endl; 

    for(int i=1;i<=n;i++) 
     cout<<x[i]<<" "; 
    // system("PAUSE"); 
    //return EXIT_SUCCESS; 
    return 0; 
} 

有关ideone.com此输入

1 5 7 8 3 9 

其写入 “超过时限”。我试过了Visual Studio中的调试器，结果如下

 
First-chance exception at 0x001c14d9 in max_heap.exe: 0xC00000FD: Stack overflow. 
Unhandled exception at 0x001c14d9 in max_heap.exe: 0xC00000FD: Stack overflow. 
First-chance exception at 0x001c14d9 in max_heap.exe: 0xC0000005: Access violation writing location 0x002c0ffc. 
Unhandled exception at 0x001c14d9 in max_heap.exe: 0xC0000005: Access violation writing location 0x002c0ffc. 
The program '[6044] max_heap.exe: Native' has exited with code -1073741819 (0xc0000005). 

什么错？

Answer 1

您的max_heapify将始终以另一个递归结束。任何控制路径都不会发生终止。这会导致您的堆栈溢出。