スタック

関数呼び出しとくに 再帰的関数呼び出しはスタックをもちいて実現されている.

このことを理解するためにまずスタックとはなにかを説明し, それから再帰がどのようにスタックを用いて実現されて いるか説明しよう.

スタックは, データを push 操作で格納し, pop 操作で データを取り出すオブジェクトである (またはデータ構造と理解してもよい). push, pop は先いれ, 先だし機能 (FIFO, First In, First Out) をもつ. たとえば, データ 1, 2, 3 を順番に push すると, pop したときは, 3, 2, 1 の順番でデータを取り出すことが可能である. スタックは次のプログラムのように配列(ベクトル)を用いると容易に 実現可能である.

$$\stackrel{\mbox{\rm push\ 10}}{\longrightarrow} \begin{arra... ... 30 & \\ \hline & 20 & \\ \hline & 10 & \\ \hline \end{array}$$

$$\stackrel{\mbox{\rm pop}}{\longrightarrow} \begin{array}{\v... ...\hline & {\rm Hello} & \\ \hline & 10 & \\ \hline \end{array}$$

/* $ stack.rr,v 1.2 2001/01/28
   02:22:03 taka Exp $ */
Stack_size = 100$
Stack_pointer = 0$
Stack = newvect(Stack_size)$

def init() {
  extern Stack_pointer;
  Stack_pointer=0;
}

def push(P) {
  extern Stack_size,Stack_pointer, 
         Stack;
  if (Stack_pointer>=Stack_size){
    error(" stack overflow. ");
  }
  Stack[Stack_pointer] = P;
  Stack_pointer++;
  return(Stack_pointer);
}

def pop() {
  extern Stack_size,Stack_pointer, 
         Stack;
  if (Stack_pointer <= 0) {
    print("Warning: stack 
      underflow. Return 0.");
    return(0);
  }
  Stack_pointer--;
  return(Stack[Stack_pointer]);
}

    

実行例:

[366] push(10);
1
[367] push(20);
2
[368] push(30);
3
[369] pop();
30
[370] pop();
20
[371] push("Hello"); 
2
[372] pop();
Hello
[373] pop();
10
[374] pop();
Warning: stack underflow.  Return 0.

push, pop を用いると, 次のようにスタック電卓を 簡単に作ることが可能となる. スタック電卓は, 式を後置形式で入力すると計算する 電卓である. 後置形式は, 演算子を最後に書く形式であり, 括弧を必要としない. たとえば, 後置形式の

2     3     +     5     *     =

は, (2+3)*5 を意味する. スタック電卓では 2 と 3 を スタックに push, + がきたら, スタックより 2 個データを pop し, 足した結果を スタックに push, * がきたら, スタックより 2 個データを pop し, かけた結果を スタックに push, = がきたら, データをスタックより pop して, 印刷する.

スタック電卓のプログラムは図 12.2 に掲載する.

図 12.2: スタック電卓 casio.rr

関数 casio() は, スタック電卓である. 数字は 1 桁した利用できない. セミコロン ; を行の始めへ入力すると 終了する.

例

[365] casio();
2 3 + =           入力
Answer=5          答え
;
0
[366] casio();
2 3 + 9 * =       入力
Answer=45         答え
;
0
[367]

さてスタックを用いて再帰を実現するには, 関数の実行前に局所変数を スタック上に確保し, 再帰呼び出しの実行が終った時点で, 局所変数をスタックから消去 ( pop ) すればよい. また関数を呼び出す前に戻り番地もスタックに格納しておく必要がある. これが, 関数が生成, 消滅している内部的仕組みである.