第３話 再帰的呼び出しによる1からnまでの和
#include<stdio.h>
int f(int n); //『分身の術』とコンソールにさせる社員
int main(){
int n;
printf("n=");
fflush(0); //pirntfを先に実行させるためのお呪い
scanf("%d",&n);
printf("1からnまでの和=%d",f(n));
}
int f(int n){
if(n-1<0)return(0);
n=f(n-1)+n; //自分が自分を呼び出す。
return(n);
}
コピペ用添付ファイル
実行画面
n=10
1からnまでの和=55
解説
fはたったの３行しかないのに、
とても難解です。
自分が自分を呼び出す、と注釈文には書いてあります。
自分が自分を呼び出す・・・
f()がf()を呼び出すのですから、
この言い方は正しいように見えます。
ですが、
正確に言うと呼び出すf()と呼び出されるf()は次元が違います。
次元が違うというには、呼び出される人形は、
あくまで、自分の中に入れ子に作った人形で、
姿は同じですが、異なる人形であることを意味しています。
次元が違うということについて、
前にeclipse c++ 入門で書いていますので、
それを参照したいと思います。
−−−一部を変えて参照−−−
私は、関数の再帰的呼び出しをいつも
入れ子式人形の比喩で説明します。
ロシアのマトリョーシカ人形（
ウィキペディアより）や七福神人形は、入れ子式人形になっています。
関数が自分を呼び出すのは、
外側の人形がひとつ内側の人形を呼び出すのに相当します。
自分が自分を呼び出すといっても、
基本的に自分と同じ形態の内側にある人形を呼び出しているのです。
関数の再帰的使用を関数の自己再帰と呼ぶ場合もありますが、
あくまで自分と基本的に同じ仕組みをした入れ子式人形の内側への進展です。
自分が自分を呼び出すとき、呼び出す自分と呼び出される自分は、
入れ子式人形とそのひとつ内側の人形に対応します。
呼び出す自分が外側の人形であり、呼び出される自分は内側の人形なのです。
同じ自分でも異なる人形です。
次元が違うというのは、同じ形態の入れ子式人形であっても、
内側の人形から見ればひとつ外側の人形、
外側の人形から見ればひとつ内側の人形というように、
違う人形であることを指しています。
入れ子式の人形の話はもちろん比喩ですが、
まさに関数の再帰的呼び出し＝関数の自己再帰と同じ構造をもっています。
より内なる自己へと遡及していって一番小さい人形にたどり着いたときに、
自分の本質を発見するのです。
今のプログラムにおいては、自己の本質とは0です。
一番小さい人形まで遡及した後はじめて、
0をいう値を発見しそれがreturnによって返されます。
どこに返されるかというと内側から２番目の人形へとです。
ｎは実は次元番号を示しています。
内側から数えて１番目の人形f(0)が、
内側から数えて２番目の人形f(1)に0の値を返します。
２番目の人形f(1)はその0の値にnの値1を加えた値1を改めてnの値として、
内側から３番目の人形f(2)にそのnの値1を返します。
３番目の人形f(2)は、２番目の人形f(1)から返ってきた値1にnの値2を加えた値3を４番目の人形f(3)に返します。
４番目の人形f(3)は、３番目の人形f(2)から返ってきた値3にnの値3を加えた値6を５番目fの人形f(4)に返します。
５番目の人形f(4)は、人形f(3)から返ってきた値6にnの値4を加えた値10を６番目の人形f(5)に返します。
・
・
・
つまり、今の動きを見ると
0+1+2+3+4+5+6+7+8+9+10
というわけです。
ｎまでの和を求めるプログラムは、
f(n)→f(n-1)→・・・→f(1)→f(0)
という自分の内なる本質への遡及と
f(0)→f(1)→・・・→f(n-1)→f(n)
逆遡及を通して、実現しているのです。
1番外側の人形から次第に内側の人形に遡及し、
自分の内なる本質0を発見すると、
逆遡及の旅が始まります。
１番目の人形f(0)の本質0が返されると、
はじめて２番目の人形f(1)の本質が1であることが分かります。
２番目の人形f(1)から本質1が３番目の人形f(2)に返されて、
はじめて３番目の人形f(2)の本質6が見いだされます。
３番目の人形f(2)から本質6が４番目の人形f(3)に返されて、
はじめて４番目の人形f(4)の本質10が見いだされます。
以下同様に繰り返されて、
1番外側の人形f(n)の本質nまでの和の正体が明らかになるのです。
−−−以上１部を変えて引用ーーー
上の引用だと、
最初から最後まで入れ子式の人形が10個入っているように、
読めてしまいますが、正確には人形が呼び出した瞬間にはじめて、
分身が内側に発生しますし、呼び出されて発生した人形は、
仕事を終えると消えてしまいす。
言い忘れていましたが、関数は呼び出されたときに、
はじめてこの世に生まれ、
仕事を終えると消滅の運命を辿るのです。
ですから、人形の個数は、
0個→1個→2個→3個→・・・→11個→10個→9個→・・・→１個→0個
1個目が発生するのは、
社長mainから、
printf("1からnまでの和=%d",f(n));
と呼びだれたときです。
そして、2個目の発生＝1個目の分身の発生は、f()がf()をはじめて呼び出した瞬間です。
では、皆さん今回のnの和を参考にしてnまでの積すなわちn!を求めるプログラムを考えて下さい。
第２話へ 第４話へ
