函数呼出とスタック

実際のプログラムでは, 函数呼出があるとスタックの構造が使われます. 函数の呼出をすると, プログラムの制御を呼び出された函数に移るわけですが, 呼び出される直前の状態を保存するために, その内容をスタックに積み(pushして) 呼び出された函数に制御が移るのです.

void fun2()
{
     ...
}
void fun1()
{
    double b=0.0;
    fun2();
}
main()
{
    int a=1;
    fun1();
}

上のような例だと, main() でfun1() が呼び出されたときに main の変数の値 (例だと, a=1)がスタックに積まれ, そのときの状態が保存されます. 次に fun1() で fun2()が呼び出されたときに,fun1()の変数(例だと, b=0.0)が, スタック(の main() の変数の上)に積まれ, それまでの状態が保存されます.

より典型的な例が, 関数の再帰呼出です. 以前の講義で述べた和を 再帰的に計算するプログラムを例に取ります.

int sum(int n)
{
    if (n==1)
        return 1;
    else
        return n+sum(n-1);
}

sum(3) の計算は, 次のように行われます.

sum(3)= 3 + sum(2) = 3 + (2 + sum(1)) = 3 + (2 + 1)

これは, 模式的には次の図のような事がコンピュータ内部で起こっているのです.

すなわち, 3, 2, 1 と順にスタックの中に入れていき, 1が来た時点で 上から計算して来ます.

実際のコンピュータでは, スタックの資源には限りがあります. 例えば, 巨大な再帰呼び出しをすると, stack overflow で計算の 途中でエラーになります. 皆さんの環境では shell がその制限を与えます.

e023199@cc> limit
cputime         unlimited
filesize        unlimited
datasize        131072 kbytes
stacksize       2048 kbytes
coredumpsize    unlimited
memoryuse       253056 kbytes
memorylocked    84352 kbytes
maxproc         160 
openfiles       64

と言う風に出力されますが, この stacksize が使えるスタックの大きさ を表しています.