なぜ私の再帰的コードはスタックオーバーフローエラーを引き起こしますか？

Question

このコードは、「アルゴリズムの紹介」という本で与えられています。このために私はそれが "超過時間制限" の書き込みideone.comでこの入力

1 5 7 8 3 9 

について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; 
} 

を使用しました。 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は常に別の再帰で終了します。いずれの制御経路にも終端は生じていない。これにより、スタックオーバーフローが発生します。