目的
Javascriptにおける再帰関数を調べていて、みなさんがあまりにことも無げに説明されていてついていけなかった人(=自分orz)のため、再帰関数の概念がつかめるように記します。
イメージはいいんだよ、実用方法を知りたい!といった方は、本記事よりこちら等を参照していただけると
http://qiita.com/chuck0523/items/2c40a5da90a1d73ab956
再帰関数とは
returnと関数を組み合わせることで、関数が自分の関数を参照していく方法です。
再帰関数はどう動くのか
再帰関数のイメージが分かりづらい原因の一つに、変数への格納がないので、結果は出てくるけど動きが読めないことにあります。
言葉で説明しても分かりづらいので、ソースを見てみましょう。
今回は階乗処理ができる関数を使います。
階乗は指定した値が1になるまで、全ての値を掛け算していく処理
例)3の階乗は3*2*1
function A (n){
if (n != 0){
return n * A (n-1);
}
else{
return 1;
}
}
console.log(A(2)); //結果:2
再帰関数を使い、nの値を 2 * 1 と処理しているだけなのですが、これだけ見ているといまいちピンときません。
次に解説と併せて、return文で省略されている関数を展開します。
function A (n){
if (n != 0){
return n * A (n-1){ //処理1 n:2 戻り値:1 引数:1 結果:2
if (n != 0){
return n * A (n-1){ //処理2 n:1 戻り値:1 引数:0 結果:1
if (n != 0){
/*引数のnが0になっているためこれ以上関数は実行されない*/
}
else{
return 1;
/*エンドポイント return 1という不自然な戻りは、ループを終わらせるため*/
}
};
}
else{
return 1; //この時点では使われない
}
};
}
else{
return 1; //この時点では使われない
}
}
console.log(A(2)); //結果:2
関数内で2つのfunction A
が動いていることがわかったかと思います。
(このような動きをするため、「再帰関数」と呼ばれています。)
ここで、ポイントになるのは「引数」「エンドポイント」「戻り値」です。
再帰関数のイメージは実際の処理順番とは関係なく、引数、エンドポイント、戻り値の順番で追ってみると、処理が分かりやすくなります。
1.引数
引数は関数Aの中に関数Aを生成するたびn-1
されており、処理が重なるほどnの値は小さくなっていることが分かります。
そのため
return n * A (n-1)
がある限り、上記はn-1の引数を作りながら「再帰(関数の中に関数を作る処理)」を続けます。
2.エンドポイント
では、終わりがないのかというと一番不自然に存在していたreturn 1が
この再帰の終着点になります。
つまり
if (n != 0)
の中でしか関数は実行されないので、nが0になった段階でreturnは1になり、再帰が終わるのです。
3.戻り値
再帰は終わったけど、じゃあ結果はどうなるの?となります。
エンドポイントで再帰関数の戻り値が確定するため、一番内側の関数から逆算していくことでようやく動きが分かります。
処理2
状態 : n=1 Aの戻り値=1(エンドポイントの戻り値)
式 :n * A (n-1)
= 1 * 1
戻り値(結果): 1
↓
処理1
状態 : n=2 Aの戻り値=1
式 :n * A (n-1)
= 2 * 1
戻り値(結果): 2
↓
最終的な戻り値
2
という流れで概念的にはエンドポイントから順に処理されて、最終のreturnにつながってくる、というのが私がイメージしやすい再帰関数の流れです。
最後に
私としてはなかなか使う機会も少なそうな再帰関数ですが、もしこれから使いたいという方が少しでも再帰関数をイメージしやすくなれば幸いです。