再帰関数(再帰呼び出し)を利用してみる

はいどーもニートのお勉強タイムです。
本日はタイトルにも示している通り再帰関数について書きます。

再帰関数ってなんやねん

そもそも再帰関数って何かご存知でしょうか?
この再帰関数君、実のところ僕もあんまり意味がわかっていなかったのですが、本日ようやく理解できました。
善は急げということで、理解できたことをまとめているのがこの記事なんですね。

まあそんなことは多くの人にとってどーでもいいことなので、ズバリ端的に再帰関数とは何かを言い表します。
再帰関数とは「Aという関数内でAという関数を呼ぶ関数のこと」です。
少しわかりにくいですね。
では、再帰呼び出しとは何でしょう。
こっちのほうがわかりやすいです。
「Aという関数内で、同じAという関数を呼ぶこと」です。
最もシンプルな例を挙げるなら、以下のようなコードとなるでしょう。

function hoge(){
hoge();
};

とはいえこれでは全く役に立たない(と言うか実行時にスタックオーバーフローが起きる)ので、もう少し実践的な内容を以下で取り扱います。

配列内の数字を全て足す関数を考える

あなたは今、配列内に存在する全ての数字を足したいとします。
「なあに、そんなこと簡単さ! for-ofを覚えた今の僕ならね☆」
本当にそうでしょうか?
例えばこのような配列が存在していた場合どうしましょう?

var hoge = [1,2,[3,4,5,6,[7,8],9],10];

愚直にfor-ofを使った場合、以下のようなコードができます。

var test = function(array){
var result = 0;
for(var element of array){
result += element;
}
return result;
};
var hoge = [1,2,[3,4,5,6,[7,8],9],10];
console.log(test(hoge));

実行すると、「33,4,5,6,7,8,910」という結果になります。
こりゃ使い物になりませんね。

問題は、配列内に配列が存在している場合、うまく計算することができていないことです。
この問題をクリアするための方法を考えてみます。

配列を展開する

配列内に配列があるのなら、配列が見つかったとき配列を展開して計算すればよいのではないでしょうか?
例えば以下のようなコードになるでしょう。

var test2 = function(array){
var result = 0;
for(var element of array){
if(Array.isArray(element)){
for(var child of element){
result += child;
}
}else{
result += element;
}
}
return result;
};

ですがこのコードには重大な欠陥が一つあります。
それは、二重の入れ子までの配列なら確かにうまく機能しますが、三重以上に入れ子になっていた場合はうまく計算できないことです。
これを解決するには、配列の入れ子分だけfor-ofも入れ子にすればいいのですが、著しく可読性が落ちます。
また、JavaScriptはブロックスコープを持たないため、入れ子内で思わぬ変数名の衝突が起き、バグの原因となるかもしれません。
これはよろしくないですね。

注*letを使えばブロックスコープを持つこともできます。

再帰関数を使って解決する

そこで再帰関数の登場です。
まずはコードを示します。

var test = function(array){
var result = 0;
for(var element of array){
if(!isNaN(element)){
result += element;
}else{
result += test(element);
}
}
return result;
};

だいぶんすっきりとして読みやすいですね。
先ほどのコードと変わっていることは、数字でない場合(ここでは配列のみしか想定していない)にtest関数を呼び出していることです。
このtest関数とは、見ればわかるように今まさに実行されている関数のことです。
つまり再帰呼び出しです。

シンプルですが、このコードは配列が何重の入れ子になっていたとしても上手に計算してくれます
では内部で一体なにが起きているのでしょう?
それを見ていきます。

再帰呼び出しの内部で何が起きているのか

先ほども書いたように、配列の要素が数字でない場合はtest関数が再び呼ばれます
その結果、要素の配列が再びtest関数に渡され、for-ofループで回されることになります。
その最後の結果がreturnされ、元の関数に値として返されます(result += test(element);の部分)。

注*ここでは配列の要素は必ず配列か数字のどちらかだと想定しています。

より詳しく挙動を見る

以下の配列をtest関数に渡すとします。
var hoge = [1,2,[3,4,5,6,[7,8],9],10];
test関数はhoge配列の要素を分解し、まず一番目の要素、すなわち1を!isNaN(element)の振るいにかけます。
1は数字であるので、そのままresultに足されます。
二番目の要素すなわち2も同じような流れです。
ここまでは大丈夫でしょう。

三番目の要素すなわち[3,4,5,6,[7,8],9]は少し複雑です。
この要素は数字ではないため、result += test(element);が実行されます。
このとき、elementには[3,4,5,6,[7,8],9]という配列が渡されます。
すると第二のtest関数に処理が移行し、無名配列(と僕は勝手に呼んでいますが、要はhoge配列の子要素です)の要素が振るいにかけられます
このとき、元のtest関数の処理が終了するわけではありません。
一時的に第二のtest関数に処理が移行しているだけです。

さて第二のtest関数内では、一番目から四番目の要素まではただの数値です。
すなわちresult += element;で普通に計算されます。
しかし五番目の要素は配列のため、ここで第三のtest関数が起動します。
無名配列[7,8]が第三のtest関数の引数として渡され、処理が始まります。
この無名配列[7,8]の各要素はただの数字のため、for-ofループは素直にresultに数字を足していくだけです。
その足された結果(第三のtest関数のresult)がretrunされ、第二のtest関数のresultに足されます。

ここで処理が第二のtest関数に戻ることに注意してください。
第二のtest関数は最後の要素の9をresultに足し、for-ofループを終了させます。
結果として第二のtest関数もreturn result;し、無名配列[3,4,5,6,[7,8],9]に対する処理が全て終了します。
この処理の結果は第一のtest関数のresult += test(element);に渡され、第一のtest関数は次のループ、すなわち最後の要素10をぶん回すこととなります。

そうして最終的に全ての数値を足し、無事めでたく55と数値が得られることになります。

再帰関数は重いらしい

再帰関数の説明は以上で終わりですが、一般的に再帰関数は通常のforループよりも重いらしいです。
なので、むやみやたらと再帰関数を利用するのではなく(覚えたばかりなので、僕もどこかで使いたいのですがw)、どうしても必要な場合にのみ再帰関数を用いるのがよいようです。

と、こんな感じで再帰関数についての説明を終わります。
最近JavaScriptについて色々と書いているので、カテゴリにJavaScriptを増やしました。
いやだからどうってことはないですが。

ほなそんな感じで、また。

フォローする