8-3. 再帰呼び出し
Ｃ言語では再帰呼出しができます。処理の流れというか再帰呼出しを使うと印刷したソースを見ただけでの状況把握がややこしくなるのと、オーバーヘッドが増えて実行速度が多少遅くなる。さらに失敗した時無限にメモリーを食らうという３つの理由であまりつかってないのですが(^^;;
数学関係で数列や階乗の処理ではソースコードをコンパクトにできます。
◇再帰呼出しとは？
再帰呼出しとはある関数がその関数内で自分自身を呼び出すことをいいます。
因みに、中で使用する変数は自動変数、引数として値を渡すことです。
(まだポインターをやってないので今までどおりの方法)
これは再帰呼出しの性質上の問題で静的変数はプログラム実行中の間メモリーを
解放しないので再帰呼出しをした場合呼び出した回数だけメモリーを消費して最悪の場合システムに悪影響が及ぶ事になります。
ポインターについても余計な処理が必要になり複雑化するだけなのでこの２つは使わないことにします。
◇階乗の計算
まず、手始めに階乗の計算を行うプログラムを書きます。
その前に、階乗について少し説明します。
階乗とは、
１×２×３×４×５×６×・・・×(ｎ－１)×ｎ
のように１からｎまでの数を掛合わせたものをいいます。
この時、ｎの階乗をｎ！と表します。
ｎ！＝１×２×３×４×５×６×・・・×(ｎ－１)×ｎ
という等式が成り立つものをｎの階乗ということにします。
◇サンプルプログラム
それでは早速サンプルプログラム。
#include<stdio.h>
int func(int);
main()
{
int n=5;
int i;
for(i=1;i< =n;i++)printf("%2d! = %10d\n",i,func(i));
}
int func(int n)
{
if(n==1)return 1;
else return n*func(n-1);
}
/* 結果
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
*/
※ＬＳＩ－Ｃ等ＤＯＳ系コンパイラご使用の方はオーバーフロー防止のためintの代わりにlongの使用をオススメします。
◇解説
さて、上のプログラムはどこでもある代表的なものなのですが・・・
再帰呼出しを使ってコンパクトにしていますが返って解読しにくいような感じになっています。というよりこの程度のプログラムは再帰を使うまでも無いのですが・・・
#include<stdio.h>
main()
{
int n=5;
int i,k=1;
for(i=1;i< =n;i++){
k=k*i;
printf("%2d! = %10d\n",i,k);
}
}
これで十分だったりします(爆)。まあアルゴリズム的に別物なのですが・・・という事で階乗の計算の解説ではなくあくまで再帰呼出しの流れの解説に留めます。
あとｎ＝５にして５階層にしてしまうとだらだらと解説が長くなるので、ここではｎ＝３にしておきます。そしてfor文を使っている為実際のプログラムでは１！，２！，３！の全てについて計算を行いますが解説のためあえて３！の時だけに限定します。
ということで、for文を外しトレースの為、随所にprintf()を追加しました。
#include<stdio.h>
int func(int);
main()
{
printf("3! = %d\n",func(3));
}
int func(int n)
{
int fact;
printf("第%d階層\n",4-n);
if(n==1) {printf("第%d階層(終)\n",4-n);return 1;}
else {fact=n*func(n-1);printf("第%d階層(終)\n",4-n);return fact;}
}
/* 結果
第1階層
第2階層
第3階層
第3階層(終)
第2階層(終)
第1階層(終)
3! = 6
*/
それでは詳細な説明に参ります。
第1階層：
ここはfunc()が呼ばれた最初の部分です。ｎの値は３なのでｎより１少ない値を引数として自分自身を呼び出します。
第2階層：
ここは第１階層のfunc()によって呼び出されました。ｎの値は２です。
さらにｎを１減らし自分自身を呼び出します。
第3階層：
ここでｎが１になったので、これ以上自分自身を呼び出す事はなくなります。
第3階層(終)：
よってif(n==1)が成立し１という値を返します。
第2階層(終)：
第３階層より値(１)が返ってきたのでｎ(２)を掛けて上の階層に返します。
第1階層(終)：
第２階層より値(２)が返ってきたのでｎ(３)を掛けて戻り値とし終了します。
よって最終的に戻ってきた値が３！の答えになります。
図で表現した方が良いのですが、書き辛かったので省略してしまい、お粗末さまでございました。m(__)m