2013/02/12

C言語 関数の再帰呼び出し

出来れば使わない方がよさそうな関数の再帰呼び出し。 再帰呼び出しは、ある関数が処理中に、自分自身を呼び出す処理のこと。 通常はfor文で実現できるので、コードの見やすさ、処理スピードを考えると、なるべくforで実現した方がよさそう。中には再帰でしか実現しにくいアルゴリズムもあるようだが。 以下は再帰呼び出しをあえて使ってみた。

再帰呼び出し

#include <stdio.h>
/* 再帰呼び出し */
void recursivecall(int n) {
  if (n < 5) {
     printf("recursivecall() enter\t%d\n", n);
     recursivecall(n + 1);
     printf("recursivecall() exit\t%d\n", n);
  }
}

int main(void) {
  recursivecall(0);
  return 0;
}
ecursivecall()という関数を再帰呼び出しするプログラム。メイン関数からはじめにrecursivecall()が呼ばれてインスタンス化される。さらにrecursivecall()の中でrecursivecall()が呼ばれる。これを4回繰り返したら、ひとつずつ抜け出してくるという仕掛け。再帰呼び出しというと自分自身を呼び出すと書かれている本が多いけど、どうも新規に自分と同じものを作り出して、入れ子になっていると考えた方が自然なような気がする。
recursivecall() enter   0
recursivecall() enter   1
recursivecall() enter   2
recursivecall() enter   3
recursivecall() enter   4
recursivecall() exit    4
recursivecall() exit    3
recursivecall() exit    2
recursivecall() exit    1
recursivecall() exit    0


再帰呼び出しで黄金比を求めてみる

#include <stdio.h>
#include <math.h>

double goldenratio(int n) {
  double f = 0;
  if (n > 0) {
     f = sqrt(1 + goldenratio(n - 1));
     printf("golden ratio:%d\t%10.11f\n", n, f);
  }
  return f;
}

int main(void) {
  goldenratio(20);
  return 0;
}
以前電卓で計算した黄金比を再帰呼び出しにしてみた。メイン関数からは呼び出し回数を指定している。20回ほど繰り返せば、そこそこの精度の黄金比が求められた。ちなみに表示は一番深いgoldenratio()関数から表示しています。最後の精度の高いgolden ratio:20は一番初めに呼び出したgoldenratio()関数となる。このへんがややこしい。
golden ratio:1  1.00000000000
golden ratio:2  1.41421356237
golden ratio:3  1.55377397403
golden ratio:4  1.59805318248
golden ratio:5  1.61184775413
golden ratio:6  1.61612120651
golden ratio:7  1.61744279853
golden ratio:8  1.61785129061
golden ratio:9  1.61797753093
golden ratio:10 1.61801654223
golden ratio:11 1.61802859747
golden ratio:12 1.61803232275
golden ratio:13 1.61803347393
golden ratio:14 1.61803382966
golden ratio:15 1.61803393959
golden ratio:16 1.61803397356
golden ratio:17 1.61803398406
golden ratio:18 1.61803398730
golden ratio:19 1.61803398830
golden ratio:20 1.61803398861


C言語 ANSI C89 Meadow & MinGW GCC 目次