概要
自分が今作っているプログラムで再帰を知る必要がありそうだなと思ったので、階乗を用いてどういう処理が流れているのが改めて学習してみました。
対象読者
- 学生時代に数学が赤点
- 数式を見ても意味がわからない
- 学生時代に再帰を学んだがよくわかっていないままの人
階乗とは？
$n! = (n-1) × (n-2)・・・$で表されるものです
詳しくはここらへんを見るといいと思います
[階乗]
(http://www.geisya.or.jp/~mwm48961/kou2/factorial1.htm)
ここも結構わかりやすかったです
再帰呼出し
nは任意の数字です プログラムで factorial(5)とかで実行したら$n=5$になります
ビックリマーク(エクスクラメーションマーク)は階乗を意味する記号だと思ってください
$5!$の$!$は$5×4×3×2×1$を省略した書き方なだけです
これだけだとよくわかりませんが実際に例を見てみるとわかりやすいと思います
たとえば、5の階乗を求める場合の答えは5を含めた5~1までをすべて掛けたものの合計です
5! = 5 × 4 × 3 × 2 × 1 = 120
4! = 4 × 3 × 2 × 1 = 24
再帰のサンプルプログラム(階乗)
実行環境を用意するのが簡単なのでjsで書いてみました
PlayCode - Code Sandbox. Online Code Editor.
このサイトがお手軽に実行できるので楽です
function factorial(n){
if(n == 0) return 1;
return n * factorial(n - 1);
}
// 120
console.log(factorial(5));
ググるとこういうプログラムがいっぱい出てきます
ちなみに再帰は終了条件を書かないと永遠に返ってこないので軽く死にます
階乗のパターンだと$n-1$で呼び続けるので、最終的に0を呼ぶことになります
その時にreturn 1をしてあげて終わらせていますね
コピペだけだとどういう過程で120になるのかよくわかっていないので処理を追ってみます
処理を追う
とりあえず標準出力を増やしてどういう流れで動いているのか可視化してみることにします
function factorial(n){
console.log('factorial(' + n + ')実行');
if(n == 0) {
console.log('n==0で再帰終了');
return 1;
}
const ans = n * factorial(n - 1);
console.log(ans);
return ans;
}
factorial(5);
結果
factorial(5)実行
factorial(4)実行
factorial(3)実行
factorial(2)実行
factorial(1)実行
factorial(0)実行
n==0で再帰終了
1 // 1 × 1
2 // 1 × 2
6 // 3 × 2
24 // 4 × 6
120 // 5 × 24
こうなりました
よくわからないので標準出力の最初のansから追ってみます
- 1回目は$1 × 0 = 0$
- ではなく0の場合
return 1しているので$1 × 1 = 1$
- ではなく0の場合
- 2回目は$2 × 1 = 2$
- 3回目は$3 × 2 = 6$
- 4回目は$4 × 6 = 24$
- 5回目は$5 × 24 = 120$
こう見るとなんかわかってきた気分になれますね
要はこの数式の
5! = 5 × 4 × 3 × 2 × 1 = 120
右の部分から掛け算していってるってことです
最終的にこうなるってことですね
const ans = n * factorial(n - 1);
// 5の階乗を再帰関数で求めた場合の最終的な掛け算は↓と同義
const ans = 5 * 24;
まとめ
- 再帰がどういう流れで動いているかわからない場合は標準出力を駆使しよう
- 先人のプログラムをコピペして実装するのもいいが、流れを理解しないと自分のやりたいことがやりにくいぞ！
- 学生のうちに数学を勉強しておかないと後悔するぞ！
感想
再帰関数の流れがどういう過程で求められるのかよくわかっていませんでしたが、こうやって標準出力で追ってみるとなかなかおもしろい動きをしていることがわかりました
こういう学習過程をちゃんと記録していきたいですね