はじめに
再帰は、関数が自分自身を呼び出すという、プログラミングの中でも強力な概念です。
最初は少しとらえにくいかもしれませんが、基本を押さえてしまえば、複雑な問題を解くための頼もしい道具になります。
このチュートリアルでは、わかりやすい例を通してJavaScriptの再帰を見ていきましょう。
再帰とは？
再帰とは、関数が直接的または間接的に自分自身を呼び出すことを指します。
ループに似ていますが、問題をより小さく、扱いやすい部分問題に分解していく点が違います。
例1：カウントダウン
まずは簡単な例から始めましょう。カウントダウン関数です。
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
この例では：
-
ベースケース：
numが0以下になると、関数は"Blastoff!"と出力し、自分自身を呼び出すのを止めます。
-
再帰ケース：関数は現在の
numを出力し、num - 1を渡して自分自身を呼び出します。
例2：階乗
次に、再帰の定番の例を見てみましょう。数値の階乗を計算します。
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
この例では：
-
ベースケース：
nが0または1のとき、関数は1を返します。
-
再帰ケース：関数は
nに、n - 1の階乗を掛けたものを返します。
重要な概念
ベースケース
再帰関数には、必ず少なくとも1つのベースケースが必要です。ベースケースとは、関数が自分自身を呼び出すのを止める条件のことです。
ベースケースがなければ、再帰は無限に続き、スタックオーバーフローを引き起こします。
再帰ケース
再帰ケースは、問題をより小さく、より単純にした形で、関数が自分自身をどう呼び出すかを定義します。
再帰の長所と短所
長所：
- 特定の問題に対してエレガントな解法になります。
- 数学的帰納法の考え方に似ています。
短所：
- 反復を使った解法よりも効率が悪くなることがあります。
- 再帰が深くなると、スタックオーバーフローを引き起こすことがあります。
まとめ
再帰は、複雑な問題をより小さく扱いやすい部分問題に分解することで、問題をシンプルにしてくれる貴重な手法です。
ベースケースと再帰ケースを理解することが、JavaScriptで効果的な再帰処理を書くうえで欠かせません。
さらに学ぶ：
説明
ピザ屋を経営していて、3種類のピザを提供しています：
- Margherita：$7
- Caprese：$9
- Formaggio：$10
お客さんが希望すれば、追加オプションを好きなだけ付けられます。「ExtraSauce」が$1、「ExtraToppings」が$2です。
課題は、お客さんが支払う金額を割り出すのを手助けするコードを書くことです。
ピザの値段を計算する
1つ目の引数にピザの名前を、続けて好きなだけ追加オプションを渡すと、ピザの値段をドルで計算します。
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
注文の合計金額を計算する
関数はPizzaOrderのリストを渡されて呼び出され、注文の合計金額をドルで返します。
各PizzaOrderには、pizzaプロパティ（ピザの名前）とextrasプロパティ（追加オプションのリスト）があります。
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
これは再帰では書けないと気づくでしょう。膨大な数の注文を扱うテストで、Maximum call stack size exceededが発生するからです。
心配いりません。これは意図的なものです。この関数は命令型のループを使って実装してみてください！
方法はたくさんあります。たとえばreduceやforループを使うなど、それだけに限りません。
JavaScriptのインタプリターがJavaScriptのコードを実行しているとき、どの関数に入ったか（呼び出しを始めたか）を、「スタック」と呼ばれるデータ構造に記録します。
関数が戻る（終了する）と、その関数はスタックから取り除かれます。
しかし、このスタックのサイズには限りがあります。
よくある間違いは、終わらない再帰関数です。
それぞれの呼び出しはスタックに積まれますが、それが戻る前に、また別の呼び出しがスタックに積まれます。
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
このエラーのスタックトレースには同じ行が何度も現れます。関数が自分自身を呼び出しているのですから、当然です。
ほとんどの場合、実際の用途はありませんが、スタックがどれくらいの高さになるかは調べられます。
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
同期の再帰関数によって引き起こされるコールスタックのエラーには、実行可能な解決策が2つしかありません：
- スタックの限界に達する前に関数が戻るようにします。ふつうは、基底ケースを追加したり修正したりします。
- 再帰関数を命令型のループに書き換えます。ループの本体は、関数に入ることなく実行されるので、スタックを増やしません。
学習演習
