第２話 関数の再帰的使用による階乗の計算
階乗プログラミング例
#include<iostream>
using namespace std;
int f(int n);
void main(){
int n;
cout<<"１からいくつまでの積？"<<endl;
scanf("%d",&n);
cout<<"1から"<<n<<"までの積は"<<f(n)<<endl;
}
int f(int n){
if(n==1)return(1);
n=n*f(n-1);
return(n);
}
前話で自分を呼び出すという言い方をしました。
自分が自分を呼び出す・・・
f()がf()を呼び出すのですから、
この言い方は正しいように見えます。
ですが、
正確に言うと呼ぶ出すf()と呼び出されるf()は次元が違います。
私は、関数の再帰的呼び出しをいつも
入れ子式人形の比喩で説明します。
ロシアのマトリョーシカ人形（
ウィキペディアより）や七福神人形は、入れ子式人形になっています。
関数が自分を呼び出すのは、
外側の人形がひとつ内側の人形を呼び出すのに相当します。
自分が自分を呼び出すといっても、
基本的に自分と同じ形態の内側にある人形を呼び出しているのです。
関数の再帰的使用を関数の自己再帰と呼ぶ場合もありますが、
あくまで自分と基本的に同じ仕組みをした入れ子式人形の内側への進展です。
自分が自分を呼び出すとき、呼び出す自分と呼び出される自分は、
入れ子式人形とそのひとつ内側の人形に対応します。
呼び出す自分が外側の人形であり、呼び出される自分は内側の人形なのです。
同じ自分でも異なる人形です。
次元が違うというのは、同じ形態の入れ子式人形であっても、
内側の人形から見ればひとつ外側の人形、
外側の人形から見ればひとつ内側の人形というように、
違う人形であることを指しています。
入れ子式の人形の話はもちろん比喩ですが、
まさに関数の再帰的呼び出し＝関数の自己再帰と同じ構造をもっています。
より内なる自己へと遡及していって一番小さい人形にたどり着いたときに、
自分の本質を発見するのです。
今のプログラムにおいては、自己の本質とは１です。
一番小さい人形まで遡及した後はじめて、
１をいう値を発見しそれがreturnによって返されます。
どこに返されるかというと内側から２番目の人形へとです。
ｎは実は次元番号を示しています。
内側から数えて1番目の人形f(1)が、
内側から数えて2番目の人形f(2)に１の値を返します。
２番目の人形f(2)はｎの値２にその１をかけて、
２にしてから３番目の人形f(3)にその２を返します。
３番目の人形f(3)は、
ｎの値３に２番目の人形f(2)から返ってきた値２をかけた値６を４番目の人形f(4)に返します。
４番目の人形f(4)は、
ｎの値４に３番目の人形f(3)から返ってきた値６をかけた値２４を５番目fの人形f(5)に返します。
５番目の人形f(5)は、
ｎの値５に４番目の人形f(4)から返ってきた値２４をかけた値１２０を６番目の人形f(6)に返します。
・
・
・
つまり、今の動きを見ると
１×２×３×４×５×６×・・・×ｎ
というわけです。
ｎ！を求めるプログラムは、
f(n)→f(n-1)→・・・→f(2)→f(1)
という自分の内なる本質への遡及と
f(1)→f(2)→・・・→f(n-1)→f(n)
逆遡及を通して、実現しているのです。
1番外側の人形から次第に内側の人形に遡及し、
自分の内なる本質１を発見すると、
逆遡及の旅が始まります。
１番目の人形f(1)の本質１が返されると、
はじめて２番目の人形f(2)の本質が２であることが分かります。
２番目の人形f(2)から本質２が３番目の人形f(3)に返されて、
はじめて３番目の人形f(3)の本質６が見いだされます。
３番目の人形f(3)から本質６が４番目の人形f(4)に返されて、
はじめて４番目の人形f(4)の本質２４が見いだされます。
以下同様に繰り返されて、
1番外側の人形f(n)の本質ｎ！の正体が明らかになるのです。
２つの事例によって、
関数の再帰的使用によってfor文と同様なことができることがわかりました。
ですが、関数の再帰的使用＝関数の再帰的呼び出しのメリットは、
これには尽きません。
関数の再帰的使用＝関数の再帰的呼び出しの最大の特徴は、
コードをいじることなく、
１０次元ループでも１万次元ループでも１京次元ループでも、
何次元ループでも可能になる点です。
コードを書き換えることなく、
ｎの値をコンソール上から入力し直すだけで、
ｎ次元ループができるのです。
for文を入れ子式に１京回も繰り返すことは不可能ですが、
関数の再帰的呼び出しなら
コードを変更することなしに可能なのです。
このことを確認するためにｎ次順列生成プログラムを
関数の再帰的使用によって実現してみましょう。
ｎの値は、コンソール上から取得するようにして下さい。
第１話へ 第３話へ
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ
