14

sum-of-first-n-natural-numbers議論中のプログラムは、 を使用して計算しようとしrecursionます。これは単純な式を使用して実行できることはわかっていますn*(n+1)/2が、ここでのアイデアは を使用することrecursionです。

プログラムは次のとおりです。

#include <stdio.h>

unsigned long int add(unsigned long int n)
{
    return (n == 0) ? 0 : n + add(n-1); 
}

int main()
{
    printf("result : %lu \n", add(1000000));
    return 0;
}

プログラムはうまく機能しましn = 100,000たが、 の値がそれnに増加する1,000,000と、Segmentation fault (core dumped)

以下、gdbメッセージより抜粋。

Program received signal SIGSEGV, Segmentation fault.
0x00000000004004cc in add (n=Cannot access memory at address 0x7fffff7feff8
) at k.c:4

私の質問:

  1. にハードワイヤードの制限はありrecursion depthますCか? またはrecursion depth、利用可能なスタックメモリに依存していますか?

  2. プログラムが reSIGSEGV シグナルを受信する理由として考えられるものは何ですか?

4

4 に答える 4

15

通常、制限はスタックのサイズになります。関数を呼び出すたびに、一定量のスタックが消費されます (通常は関数によって異なります)。食べた分はスタックフレームで、関数が戻ると回復します。スタックサイズは、オペレーティングシステムによって指定されているか（多くの場合、そこで調整可能）、またはプログラムでハードコーディングされているため、プログラムの起動時にほぼ固定されています。

  • 一部の実装には、実行時に新しいスタック セグメントを割り当てることができる手法がある場合があります。しかし、一般的にはそうではありません。

  • 一部の関数は、可変長配列をそこに割り当てる場合など、もう少し予測不可能な方法でスタックを消費します。

  • 一部の関数は、スタック スペースを保持する方法でテール コールを使用するようにコンパイルされる場合があります。場合によっては、すべての呼び出し (それ自体への呼び出しなど) が最後に行われるように関数を書き直して、コンパイラが関数を最適化することを期待できます。

関数の呼び出しごとにどれだけのスタック領域が必要かを正確に把握するのはそれほど簡単ではなく、コンパイラの最適化レベルに左右されます。あなたの場合、それを行う安価な方法は&n、呼び出されるたびに印刷することです。nスタック上にある可能性が高く（特に、プログラムがアドレスを取得する必要があるため-そうでない場合はレジスターにある可能性があります）、連続する位置間の距離はスタックフレームのサイズを示します。

于 2012-04-20T08:43:55.793 に答える
7

1）スタックの消費は削減され、末尾再帰の最適化として記述されることが期待されます。

gcc -O3 prog.c

#include <stdio.h>

unsigned long long int add(unsigned long int n, unsigned long long int sum){
    return (n == 0) ? sum : add(n-1, n+sum); //tail recursion form
}

int main(){
    printf("result : %llu \n", add(1000000, 0));//OK
    return 0;
}
于 2012-04-20T10:54:39.413 に答える
5

C では、再帰の深さに理論上の制限はありません。唯一の制限は実装の制限であり、通常はスタック スペースが制限されます。
(C 標準は実際にはスタックベースの実装を必要としないことに注意してください。スタックベースではない実際の実装については知りませんが、覚えておいてください。)

SIGSEGV はさまざまな原因で発生する可能性がありますが、スタック制限を超えることは比較的一般的です。不適切なポインターの逆参照は別の方法です。

于 2012-04-20T08:42:04.817 に答える
3

C 標準では、関数呼び出しでサポートされる最小の深さは定義されていません。もしそうなら、とにかく保証するのは非常に難しいですが、それはセクションのどこかに言及されているでしょう5.2.4 Environmental limits.

于 2012-04-20T09:10:57.033 に答える