プログラミング言語 C

lang

C は 関数を 再帰的 (recursion) に 使用することができる。つまり 関数は (その内部で) 関数自身を 直接 または 間接に 呼び出してもよい。

数字を 文字列に 変換する関数 print_d() を 考えてみよう。

数字の場合、逆順生成という 性質をもつ。すなわち 低い桁の数字が 高い桁の数字より 先に得られる。

(そのため 出力時には) 逆順に プリントさせなければならない。

この問題には 2つの解がある。一つは 生成した順に 配列に格納し (do-while文を使って) 逆順に プリントする方法である。

もう一つの方法が 再帰を使う 解法で、逆順生成に 対処するため、関数内部で 関数自身を 呼び出すようにする。

  1. /* print_d.c */
  2. #include
  3. /* 数字 n を 10進法で プリントする */
  4. void print_d(int n)
  5. {
  6. if (n < 0) {
  7. putchar('-');
  8. n = -n;
  9. }
  10. /* 数字 n が 負の場合 はじめに 正の整数に 変換しておく */
  11. if (n / 10)
  12. print_d(n / 10);
  13. /* 数字が 2桁以上のとき 再帰関数を 呼び出す */
  14. /* このとき int型の 除算なので 小数点以下が 切捨てとなる */
  15. putchar(n % 10 + '0');
  16. /* 高い桁から 順に プリント */
  17. }

関数が 自分自身を 再帰的に呼び出すと、それぞれの 呼び出しごとに すべての 自動変数が 一新され、以前とは まったく 独立した セットになる。

例えば print_d(123) では 最初の print_d() では n = 123 である。

第2レベルの print_d() では '12' が 渡り、つぎに そのうちの '1' が 第3レベルの print_d() に 渡る。

第3レベルの print_d() は '1' を プリントしてから 第2レベルに 戻る。第2レベルのprint_d() で '2' が プリントされ、最初のレベルへと 戻る。そして '3' が プリントされ (この関数は) 終了となるわけである。

再帰を使った もう一つの よい例が quicksort すなわち C.A.R.Hoare が 1962年に 考えだした ソートアルゴリズムである。

ある配列が 与えられたとき、 まず 1つの要素 (下のコードでは int n) を 選んだら、その要素より 小さいパートと、等しいか より大きいパートとの 2つの サブセットに 分割する。

次に 同じプロセスを 再帰的に 2つの サブセットに 適用していく。

そして サブセットが 2より 少ない 要素を もつようになれば このソートは 必要なくなり 再帰は 終了する。

  1. /* q_sort.c */
  2. void q_sort(int v[], int left, int right)
  3. {
  4. int i, last;
  5. void swap (int v[], int i, int j);
  6. if (left >= right)
  7. return;
  8. /* 配列が 2 より 少ない 要素に なったときは */
  9. /* 以下の プログラムは 実行されない */
  10. swap (v, left, (left + right) / 2);
  11. last = left;
  12. /* 分割要素を サブセットの始め = v[0] に 移動させる */
  13. for (i = left + 1; i <= right; i++) /* 分割 */
  14. if (v[i] < v[left])
  15. swap (v, ++last, i);
  16. /* for文は ここまで */
  17. swap (v, left, last); /* 分割要素を 回復 */
  18. q_sort(v, left, last - 1);
  19. q_sort(v, last + 1, right);
  20. /* 再帰関数を 使い 左右それぞれの サブセットを ソートしていく */
  21. }
  1. /* swap.c */
  2. /* スワップ関数 */
  3. void swap (int v[], int i, int j)
  4. {
  5. int tmp;
  6. tmp = v[i];
  7. v[i] = v[j];
  8. v[j] = tmp;
  9. }

再帰を使う場合、処理中の値の スタックを 保持しなければならない。そのため メモリの 節約には ならないし また 速度も (使用しないときと 比べ) 速いとはいえない。

しかし 再帰を使った プログラムでは (コード自体が) より コンパクトになり、使わない プログラムに 比べて ずっと 書きやすく また 理解するのが 容易と なることが 多い。

再帰は tree のように 再帰的に 定義される データ構造には 特に 適した 書き方である。(p105-107)