はじめに: 再帰処理は「自分で自分を呼び出す」考え方
前の記事では、配列とメモリの考え方を見ました。配列はデータを順番に並べて扱うための基本的な構造で、探索やソートなど多くのアルゴリズムの土台になります。
今回扱う再帰処理は、アルゴリズムを理解するうえで避けて通れない考え方です。再帰処理とは、関数が自分自身を呼び出す処理のことです。
最初に聞くと少し不思議に感じるかもしれません。「自分で自分を呼び出す」と聞くと、いつ終わるのか分からなくなりそうです。実際、再帰には必ず止まる条件が必要です。
再帰は、問題を同じ形の小さな問題に分けながら解くときに役立ちます。木構造、フォルダ階層、クイックソート、探索処理など、基本情報技術者試験でも実務でも出会う場面があります。この記事では、JavaScriptの短いコードを使って、再帰の流れをゆっくり確認します。
再帰処理は、関数が自分自身を呼び出すことで問題を小さくしながら解く考え方です。
まずはカウントダウンで再帰を見る
まずは、単純なカウントダウンで再帰を見てみます。
function countDown(n) {
if (n === 0) {
console.log("end");
return;
}
console.log(n);
countDown(n - 1);
}
countDown(3);このコードを実行すると、3、2、1、end の順に表示されます。
countDown(3) の中で、countDown(2) を呼び出しています。countDown(2) の中では、さらに countDown(1) を呼び出します。そして countDown(1) の中で countDown(0) を呼び出します。
ここで大事なのは、毎回少し小さな問題にしていることです。最初は3から始まり、2、1、0へと近づいていきます。再帰処理では、このように「同じ関数を呼ぶけれど、引数を変えて終わりに近づける」ことがよくあります。
再帰では、現在の処理の中から少し小さな問題として同じ関数を呼び出します。
再帰には必ず停止条件が必要
再帰処理で一番大事なのは、停止条件です。停止条件とは、これ以上自分自身を呼び出さずに処理を終える条件のことです。
先ほどのコードでは、次の部分が停止条件です。
if (n === 0) {
console.log("end");
return;
}n が0になったら、return で関数を終えます。これがあるから、countDown(3) はいつか止まります。
もし停止条件がなければ、関数は自分自身を呼び出し続けます。JavaScriptでは、関数呼び出しが深くなりすぎるとエラーになります。いわゆるスタックオーバーフローです。
基本情報の問題でも、再帰関数を読むときはまず停止条件を探すと落ち着いて追えます。「いつ止まるのか」「止まる条件に近づいているのか」を見ることが、再帰を理解する入口です。
再帰処理では、どこで呼び出しを止めるかを決める停止条件が必ず必要です。
呼び出しはスタックのように積み重なる
再帰処理は、関数呼び出しが積み重なるところが少し難しく感じられます。ここで、以前扱ったスタックの考え方が役立ちます。
次のコードを見てみます。
function show(n) {
if (n === 0) return;
console.log(`before ${n}`);
show(n - 1);
console.log(`after ${n}`);
}
show(3);このコードでは、再帰呼び出しの前に before を表示し、再帰呼び出しの後に after を表示しています。
show(3) は before 3 を表示してから show(2) を呼びます。show(2) は before 2 を表示してから show(1) を呼びます。show(1) は before 1 を表示してから show(0) を呼びます。
show(0) は停止条件によりすぐ戻ります。すると、最後に呼ばれていた show(1) の続きから実行され、after 1 が表示されます。その次に show(2) に戻り、after 2、最後に show(3) に戻って after 3 が表示されます。
つまり、呼び出しは上に積み重なり、戻るときは最後に積まれたものから順に処理されます。これはスタックの「後入れ先出し」と同じイメージです。
再帰呼び出しはスタックのように積み重なり、最後に呼ばれた処理から順番に戻っていきます。
階乗をJavaScriptで書いてみる
再帰の定番例として、階乗があります。階乗は、たとえば 5! なら 5 * 4 * 3 * 2 * 1 のように計算します。
これを再帰で書くと、次のようになります。
function factorial(n) {
if (n === 1) {
return 1;
}
return n * factorial(n - 1);
}
console.log(factorial(5));factorial(5) は、5 * factorial(4) です。factorial(4) は、4 * factorial(3) です。このように、同じ形の小さな問題へ分けていきます。
最後に factorial(1) まで来たら、停止条件により1を返します。そこから戻りながら、2 * 1、3 * 2、4 * 6、5 * 24 のように計算され、最終的に120になります。
階乗の例は、再帰の形が分かりやすい例です。「nの階乗は、nとn-1の階乗を掛けたもの」と考えられるため、そのままコードにしやすいからです。
階乗のように、同じ形の小さな問題へ分けられる処理は再帰で表しやすくなります。
ループで書ける処理もある
再帰で書ける処理の中には、ループでも書けるものがあります。階乗もその1つです。
function factorialLoop(n) {
let result = 1;
for (let i = 1; i <= n; i++) {
result *= i;
}
return result;
}
console.log(factorialLoop(5));このコードでは、for 文を使って1からnまで順番に掛けています。結果は再帰版と同じです。
では、再帰とループのどちらを使えばよいのでしょうか。答えは、処理の形によります。単純な繰り返しなら、ループのほうが読みやすいことが多いです。一方で、問題が同じ形の小さな問題に自然に分かれる場合は、再帰のほうが考えやすいことがあります。
再帰は便利ですが、呼び出しが深くなりすぎるとスタックオーバーフローの原因になります。実務では、読みやすさ、データの大きさ、安全性を見ながら使うことが大切です。
再帰で書ける処理の中には、ループで書いたほうが読みやすいものもあります。
再帰が向いている処理
再帰が向いているのは、同じ形の小さな問題が入れ子になっている処理です。
たとえば、フォルダの中にフォルダがあり、その中にさらにフォルダがある構造を考えてみます。中身をすべて調べたい場合、「フォルダを調べる」という処理の中で、見つかったフォルダに対してまた同じ処理を行うことになります。
Web開発でも、入れ子になったコメント、カテゴリ階層、メニュー構造、DOMツリーなどを扱う場面があります。1つの要素を処理し、その子要素にも同じ処理を行う、という形は再帰と相性がよいです。
また、クイックソートのような分割統治のアルゴリズムでも再帰が使われます。大きな問題を小さな部分に分け、それぞれに同じ処理を行い、結果を組み合わせる考え方です。
再帰は、同じ形の小さな問題が入れ子になっている処理で特に力を発揮します。
試験ではどう問われるか
基本情報技術者試験では、再帰処理はアルゴリズムのトレース問題として出てくることがあります。関数がどの順番で呼び出され、どの順番で戻り、最終的に何が表示されるか、何が返るかを追う問題です。
再帰関数を見るときは、まず停止条件を確認します。次に、再帰呼び出しの前に処理があるのか、後に処理があるのかを見ます。呼び出し前の処理は行きがけに実行され、呼び出し後の処理は戻りがけに実行されます。
スタックの考え方を持っていると、再帰の流れを追いやすくなります。呼び出しが積まれ、最後に呼ばれたものから戻る。このイメージが、表示順や戻り値の理解に役立ちます。
基本情報では、再帰関数がどの順番で呼ばれ、どの順番で戻るかを追う力が重要です。
実務ではどう使われるか
Web開発でも、再帰の考え方が役立つ場面があります。特に、入れ子になったデータ構造を扱うときです。
たとえば、カテゴリに子カテゴリがあり、その子カテゴリにもさらに子カテゴリがある場合、同じ処理を階層の下まで繰り返したくなります。コメントツリーやメニュー、DOMのような構造でも同じです。
ただし、実務では再帰を使えば必ずよいわけではありません。データの階層が深すぎると、呼び出しが深くなりすぎてエラーになることがあります。また、再帰に慣れていない人が読むと、ループより処理の流れを追いにくいこともあります。
そのため、再帰は「入れ子構造を自然に表せるとき」に使い、単純な繰り返しではループも検討する、という使い分けが大切です。
Web開発では、入れ子になったデータ構造をたどる場面で再帰の考え方が役立ちます。
まとめ: 再帰は問題を小さくして解く道具
再帰処理は、関数が自分自身を呼び出す処理です。問題を同じ形の小さな問題に分けながら解くときに役立ちます。
再帰には、必ず停止条件が必要です。停止条件がなければ、関数は自分自身を呼び続けてしまいます。また、再帰呼び出しはスタックのように積み重なり、最後に呼ばれた処理から順番に戻っていきます。
階乗のような処理は再帰で書きやすい一方、単純な繰り返しならループのほうが読みやすいこともあります。再帰とループは対立するものではなく、処理の形に応じて使い分けるものです。
再帰を理解すると、木構造、探索、クイックソートのような少し複雑なアルゴリズムを追いやすくなります。次の記事では、再帰とも関係の深いクイックソートをJavaScriptで見ていきます。
再帰処理を理解すると、木構造、探索、ソートのような少し複雑なアルゴリズムを追いやすくなります。
コメント