━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
再帰の考え方
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●再帰の基本

再帰の考え方の基本は「より単純な場合への問題の帰着」である．

2分木を扱う再帰では，特に「分割統治」がうまく働く．
処理対象を分割し，各部分ごとの処理結果を全体の処理に反映する．
分割を繰り返せば，いずれ，部分のない単純な対象の処理に行き着く．

●再帰関数の例

2分木を扱う典型的な再帰関数の例として，節数を求める関数を考える．

節がないとき(2分木データへのポインタが空の場合)節数は 0，
節があるとき(2分木データへのポインタが節を指す場合)木全体の節数は
左の部分木の節数 + 右の部分木の節数 + 1，とすればよい．

木全体の節数を求めるために部分木の節数を使い，部分木への分割を
繰り返すと部分木のない場合に行き着く，ということに注意する．

●再帰プログラムの例

2分木の節数を求める再帰関数が，次のプログラムファイル中にある．
節数を求める再帰関数が size() で，その実行過程を display() で表示できる．

        再帰関数のプログラム例： recursion.c recursion.py

実行すると，木を表す文字列，木の節数，節数の再帰計算の過程，が表示される．
計算過程の表示は，上から下へ向かって処理が進み，左から右へ向かって
関数呼び出しの入れ子が深くなることを意味する．

        プログラム例の実行結果： recursion-result.txt

●再帰の考え方の習得

プログラム例と実行結果をよく調べれば，再帰関数の作り方と
再帰関数の実行過程についての理解が深まる．

再帰の考え方を身に付けるには，例題プログラムを参考に，
様々な再帰プログラムに手を加えて実行過程を調べ，考察を深めるとよい．

●再帰アルゴリズムを設計するコツ

慣れないうちは，アルゴリズムの設計に取り掛かる前に，例を使って考える．

いくつかの具体例について，部分問題の解が得られていることを想定して
(木構造なら，左右の部分木の処理が済んだものと考えて)，
全体の解が部分問題の解を使ってどう計算できるかを考えるとよい．

アルゴリズムの典型例(木構造なら，先行順・中間順・後行順 の走査など)を
参考に，実際の問題解決に必要なアルゴリズムを設計する練習を積んでほしい．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/