爲什麼我的遞歸代碼導致堆棧溢出錯誤？

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將始終以另一個遞歸結束。任何控制路徑都不會發生終止。這會導致您的堆棧溢出。