next up previous contents index
: スタック : 再帰呼び出しとスタック : 再帰呼び出しとスタック   目次   索引

再帰呼び出し

階乗 $n!$ は次のような性質をみたす.

\begin{displaymath}n! = n \cdot (n-1)!, \quad 0! = 1. \end{displaymath}

ある関数のなかから, 自分自身を呼び出すことを再帰呼び出し (recursive call) という. 多くのプログラム言語では, 再帰的な関数呼び出しをみとめており, その機能を使うと上のような性質をもちいてそのままプログラムする ことが可能となる.

階乗関数の再帰的実装:

   def rfactorial(N) {
      if (N < 0) error("rfactorial: argument must be 0 or natural numbers.");
      if (N == 0) return(1);
      else {
         return(N*rfactorial(N-1));
      }
   }

上の関数定義をみればわかるように関数 rfactorial のなかで関数 rfactorial を 呼んでいる.

例 11.1   漸化式 $ x_n = 2 x_{n-1} + 1,\ x_0 = 0 $ できまる数列の $n$ 項めをもとめるプログラムを作ろう. プログラムは以下のようになる. 再帰をつかわないプログラムと比べて, ずいぶんすっきりかけていることに 注意しよう.

 def xn2(N) {
    if (N == 0) return(0);
    XN = 2*xn2(N-1)+1;
    return(XN);
 }

プログラム自体は単純であるが, 実はこのような場面で再帰をもちいるのはあまり得策ではない. メモリや実行効率の低下があるからである. 8 章で説明した関数呼び出しの仕組みを思いだそう. 関数およびその局所変数は動的に生成, 消滅を繰り返している. たとえば, 上のプログラムで xn2(4) をよぶと, xn2(3), xn2(2), xn2(1), xn2(0) がつぎつぎとよびだされ, xn2(0) の実行中には, 5 つの xn2 が実行されており, したがって局所変数 XN および 引数 N も, それぞれ 5 つ生成されている. したがって一般に, xn2(n) に対しては, 最大 $2(n+1)$ 個の変数領域が確保されることになる.

次のようなプログラムを書けば, このようなメモリの無駄使いは 生じない.

 def xn2(N) {
    XN = 0;
    for (I=0; I<N; I++) {
      XN = 2*XN+1;
    }
    return(XN);
 }

処理系によっては, このように非効率的に書かれた再帰呼び出しを 自動的に効率的な形式に変更する機能をもったものもある.

問題 11.1   フィボナッチ数とは次の漸化式できまる数列である.

\begin{displaymath}f_n = f_{n-1}+f_{n-2}, \ f_1 = f_2 = 1. \end{displaymath}

フィボナッチ数を求める再帰的なプログラム

   def fib(N) {
      if (N == 1) return(1);
      if (N == 2) return(1);
      return(fib(N-1)+fib(N-2));
   }

を考える. このプログラムは効率の悪い再帰プログラムである. 理由を述べよ. じっさい良くないプログラムであることを, 再帰を用いないプログラムと比較して確かめよ.

再帰がもっとも強力にその威力を発揮するのは, データ構造自身が再帰的な構造をもっているリスト構造の場合や, 構文解析の場合である. Quick sort なども再帰がその威力を発揮する場合である. これらについては後の節でくわしく考察する. その他, フラクタル (自己相似図形) を描くのも再帰をもちいると 簡単であることがおおい.

例 11.2   C 曲線を書くプログラムを書け. C 曲線は与えられた線分の集合に含まれる各線分を

\begin{picture}(60,20)
\put(0,20){\vector(1,-1){20}}
\put(30,10){$\Rightarrow$}
\put(50,20){\vector(0,-1){20}}
\put(50,0){\vector(1,0){20}}
\end{picture}
のように折れ線に置き換えることにより生成される 図形である. この置き換えプロセスを 1 本の線分よりスタートして, $n$ 回繰り返すと $n$ 次の C 曲線を得ることができる. 次の図は $6$ 次の C 曲線である.
\scalebox{0.5}{\includegraphics{Figures/ccurve.ps}}
この図を生成したプログラムを図 12.1 に 掲載する. プログラムのポイントは次の事実である:
$(a,b)$ および $(c,d)$ をある正方形の対角線の頂点とするとき, $((a+c+d-b)/2, (b+d+a-c)/2)$, $((a+c+b-d)/2, (b+d+c-a)/2)$ はこの正方形ののこりの頂点である. (内積と対角線の中点からの長さを考えると簡単にわかる.)
図 12.1: C 曲線を書くプログラム
\begin{figure}\par
\begin{verbatim}load(''glib'')$
def cCurve(P) {
if (length...
...
print(''Type in, for example, main(8);'')$
end$\end{verbatim}
\par
\end{figure}

問題 11.2   次のような定規を描くプログラムを再帰を用いて書け.

\begin{picture}(100,10)
\put(0,0){\line(1,0){100}}
\put(0,0){\line(0,1){10}}
\pu...
...ne(0,1){2} }
\put(62,0){\line(0,1){2} }
\put(87,0){\line(0,1){2} }
\end{picture}



Nobuki Takayama 平成15年9月12日