第９講 関数の再帰的使用
第４話 階乗を求めるプログラム
実行画面が
これはa!を求めるプログラムです。aに値を入れてエンターして下さい。
a=10
10!=3628800
となるプログラム例
#include<iostream> //入出力のために組み込む
using namespace std; //coutを使うために必要なお呪い
int f(int a);
int main() {
int a;
cout<<"これはa!を求めるプログラムです。aに値を入れてエンターして下さい。"<<endl;
cout<<"a=";
scanf("%d", &a);
cout<< a <<"!="<< f(a) <<endl;
return(0);
}
int f(int a) {
int w;
if (a - 1 >= 1)w = f(a - 1); else w = 1;
w *= a;
return(w);
}
解説
最初に、main()は１から１０までの和は何とf(10)によって関数f(10)に問い合わせています。
以下、
最初の人形（f(10)本体）は、f(a - 1)によって『f(9)の正体は何と』f(10)の分身f(9)に問い合わせます。
f(9)の正体とは、１×２×３×４×５×６×７×８×９の答えです。
つまり、f(10)がその答えがわからないと、main()の質問、
１×２×３×４×５×６×７×８×９×１０って何？に対して答えられないのです。以下同様です。
f(9)は、f(a - 1)によって『f(8)の正体は何と』f(9)の分身f(8)に問い合わせます。
f(8)は、f(a - 1)によって『f(7)の正体は何と』f(8)の分身f(7)に問い合わせます。
f(7)は、f(a - 1)によって『f(6)の正体は何と』f(7)の分身f(6)に問い合わせます。
f(6)は、f(a - 1)によって『f(5)の正体は何と』f(6)の分身f(5)に問い合わせます。
f(5)は、f(a - 1)によって『f(4)の正体は何と』f(5)の分身f(4)に問い合わせます。
f(4)は、f(a - 1)によって『f(3)の正体は何と』f(4)の分身f(3)に問い合わせます。
f(3)は、f(a - 1)によって『f(2)の正体は何と』f(3)の分身f(2)に問い合わせます。
f(2)は、f(a - 1)によって『f(1)の正体は何と』f(2)の分身f(1)に問い合わせます。
最後の分身f(1)にたどり着いて、その正体がはじめてわかります。
if (a -1 >= 0)w=f(a - 1); else w=1;
の否定部分によってw=1になり、
w*=a;
によって、
w=1*1=1;
f(1)の正体が1であることがわかります。
この1が
return(w);
によって、f(2)に返されます。
f(2)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=1;
w=1*2；
を辿りf(2)の正体が2であることがわかり、
return(w);
によって、f(2)に2が返されます。
f(3)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=2;
w=2*3；
を辿りf(3)の正体が6であることがわかり、
return(w);
によって、f(4)に6が返されます。
f(4)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=6;
w=6*4；
を辿りf(4)の正体が24であることがわかり、
return(w);
によって、f(5)に24が返されます。
f(5)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=24;
w=24*5；
を辿りf(5)の正体が120であることがわかり、
return(w);
によって、f(6)に120が返されます。
f(6)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=120;
w=120*6；
を辿りf(2)の正体が720であることがわかり、
return(w);
によって、f(7)に720が返されます。
f(7)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=720;
w=720*7；
を辿りf(7)の正体が5040であることがわかり、
return(w);
によって、f(8)に5040が返されます。
f(8)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=5040;
w=5040*8；
を辿りf(8)の正体が40320であることがわかり、
return(w);
によって、f(9)に40320が返されます。
f(9)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=40320;
w=40320*9；
を辿りf(9)の正体が362880であることがわかり、
return(w);
によって、f(10)に362880が返されます。
f(10)では
if (a -1 >= 0)w=f(a - 1); else w=1;
w*=a;
の２行から
w=362880;
w=362880*10；
を辿りf(10)の正体が3628800であることがわかり、
return(w);
によって、main()に3628800が返されます。
以上の長い過程を得てはじめて１×２×３×４×５×６×７×８×９×１０の正体がつかめるのです。
以上を簡単にまとめると
main()→f(10)→ f(9)→f(8)→f(7)→f(6)→f(5)→ f(4)→f(3)→f(2)→f(1)
と遡及していって、一番小さい人形（一番内側の人形）にたどり着いて自分の一番奥深くの正体が1であることを発見します。
この後は逆遡及を通して、
f(1)→f(2)→f(3)→f(4)→f(5)→ f(6)→f(7)→f(8)→f(9)→f(10)→main()
main()にたどり着くのですが、一番奥深い自分の本質1は、
1→1*2=1→2*3=6→6*4=24→24*5=120→120*6=720→720*7=5040→5040*7=40320→40320*9=362880→362880*10=3628800
と加工されていって、3628800に変身を遂げて、main()に戻されるのです。
さて、次の課題は任意の順列を作り出すソフトです。
順列とは１２３を例にすると、
１２３ １３２ ２１３ ２３１ ３１２ ３２１
です。
順列とは並び替えです。
これはすべての順列を求めるソフトです。
何の順列を発生させるのかをaに入力してエンターして下さい。
n=4
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
生成された順列は24個です。
となるソフトを今から開発していきますが、
これを再帰的使用でいきなり作って下さいと、
初心者に課したのでは、余りにも不親切です。
初心者どころか中級者でも悩んでしまうほど難しい課題だからです。
実行画面のように４つの数字の並びを４次順列と名付けます。
n個の数字の順列ならn次順列と呼ぶわけです。
nはnunberの頭文字です。
数学の世界では整数をnで表すことが多いので、
今までaで通してきたものをこれからはnで表すことにします。
n次順列は一般的な言い方ではなく本サイト独自な呼び方です。
まず、２次順列を関数の再帰的使用ではなく、
２次元for文で実現しましょう。
