👏

再帰処理について調べてみた

に公開
JavaScript
初心者
プログラミング
zennfes2025free
tech

再帰処理の歴史

数学的なルーツ 🌱

再帰の概念は、プログラミングよりずっと古くから数学の世界に存在していました。1930年代、クルト・ゲーデル、アロンゾ・チャーチ、スティーヴン・クリーネといった数学者たちが、計算可能とは何かを探求する中で「再帰関数」の理論を形式化しました。これは、ある関数の定義の中にその関数自身が現れるもので、現代プログラミングの再帰の直接的な理論的基礎となりました。特に、チャーチが考案したラムダ計算は、関数を第一級のオブジェクトとして扱い、再帰的な定義を自然に表現できるため、後の関数型プログラミング言語に絶大な影響を与えました。

プログラミング言語への導入 💻

再帰がプログラミングの具体的な機能として実装されたのは、1950年代後半から1960年代初頭にかけてです。

LISP: 再帰を核とした言語

1958年にジョン・マッカーシーによって開発された LISP（LISt Processing）は、再帰を言語の中心的な機能として全面的に採用した最初の主要なプログラミング言語です。マッカーシーはラムダ計算に強い影響を受けており、LISPはリスト構造を処理するために再帰を非常にエレガントに利用しました。これにより、複雑なデータ構造を簡潔なコードで操作できるようになり、特に人工知能（AI）研究の分野で広く使われるようになりました。

ALGOL 60: 主流言語への普及

一方、ヨーロッパで開発された ALGOL 60（1960年）は、より主流の手続き型言語に再帰をもたらしたという点で画期的でした。ALGOL 60は、スタックベースのメモリ管理を導入しました。これにより、関数が呼び出されるたびにその関数のローカル変数や状態がスタックに積まれ、関数が終了するとスタックから取り除かれます。この仕組みは、関数が自分自身を呼び出す再帰処理を安全かつ効率的に実現するために不可欠であり、その後の多くの言語（Pascal、C、Javaなど）の基礎となりました。

発展と現代 ✨

ALGOL 60以降、再帰はプログラミングの基本的なテクニックとして広く認知されるようになりました。

  • アルゴリズムの自然な表現: クイックソート、マージソート、木構造の探索といった多くの基本的なアルゴリズムは、再帰を用いると非常に自然かつ直感的に記述できます。
  • 関数型プログラミングの台頭: HaskellやML、F#といった関数型言語では、ループ（for文やwhile文）の代わりに再帰（特に末尾再帰）を使って繰り返し処理を記述するのが一般的です。
  • 最適化技術の進歩: 再帰はシンプルですが、呼び出しが深くなると「スタックオーバーフロー」というエラーを引き起こす弱点がありました。この問題を解決するため、コンパイラが再帰呼び出しを内部的にループ処理に変換してスタック消費を抑える「末尾再帰最適化（Tail Call Optimization）」という技術が1970年代に考案され、多くのモダンな言語で採用されています。

今日、再帰は単なるプログラミング技法の一つではなく、問題をより小さな同じ構造の問題に分割して考えるという、コンピュータサイエンスにおける重要な思考法「分割統治法」を体現するものとして、すべてのプログラマーにとって必須の知識となっています。

再帰処理とは

再帰処理（さいきしょり）とは、ある処理の途中で、その処理自身を呼び出すことを指します。プログラミングでは、関数が自分自身の関数を呼び出す形で実装され、これを「再帰関数」と呼びます。

たとえるなら、マトリョーシカ人形のようなものです。大きな人形を開けると中に少し小さい同じ人形が入っていて、それを開けるとさらに小さい人形が…と繰り返されていき、最後にはそれ以上開けられない一番小さな人形にたどり着きます。この「人形を開ける」という行為が、自分自身を呼び出す処理にあたります。

JavaScriptにおける再帰処理とは、ある関数がその処理の中で、自分自身を呼び出すことです。問題をより小さく、同じ構造を持つ問題に分割して解いていくとき非常に強力なテクニックです。

再帰の2つの必須要素

再帰関数を正しく動作させるには、必ず2つの要素が必要です。

  1. ベースケース（Base Case）: 再帰を停止させる条件です。これがないと、関数は無限に自分自身を呼び出し続け、最終的にエラー（スタックオーバーフロー）を引き起こします。
  2. 再帰ステップ（Recursive Step）: 問題を少しだけ簡単なものにし、自分自身を呼び出す部分です。

階段を上ることに例えると、「最上段に着いたら終わり（ベースケース）」と「もう一歩上る（再帰ステップ）」というルールを繰り返しているようなものです。

基本的な例：階乗の計算

数値の階乗（例: 4! = 4 × 3 × 2 × 1）を計算する関数は、再帰を理解するための典型的な例です。

function factorial(n) {
  // ベースケース: nが1以下になったら、1を返して処理を終了する
  if (n <= 1) {
    return 1;
  }
  // 再帰ステップ: n に (n - 1) の階乗を掛ける
  // ここで自分自身を呼び出している
  else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(4)); // 結果: 24

処理の流れ (factorial(4) の場合)

このコードは内部で次のように動きます。

  1. factorial(4) が呼ばれる → 4 * factorial(3) を計算しようとする
  2. factorial(3) が呼ばれる → 3 * factorial(2) を計算しようとする
  3. factorial(2) が呼ばれる → 2 * factorial(1) を計算しようとする
  4. factorial(1) が呼ばれる → ベースケースに合致！ 1 を返す
  5. factorial(2) に 1 が返され、2 * 1 = 2 を返す
  6. factorial(3) に 2 が返され、3 * 2 = 6 を返す
  7. factorial(4) に 6 が返され、4 * 6 = 24 を返す

このように、一番奥のベースケースまで到達した後、結果が逆順に返っていくことで最終的な答えが計算されます。

より実践的な例：ネストした配列の合計

再帰は、階層構造を持つデータの扱いに非常に適しています。例えば、内側に入れ子になった（ネストした）配列に含まれる数値をすべて合計する場合を考えてみましょう。

function sumNestedArray(arr) {
  let total = 0;

  for (const element of arr) {
    // 要素が配列なら、再帰的に合計を計算して加算する（再帰ステップ）
    if (Array.isArray(element)) {
      total += sumNestedArray(element);
    }
    // 要素が数値なら、そのまま加算する（ベースケースの一部）
    else if (typeof element === 'number') {
      total += element;
    }
  }

  return total;
}

const nestedNumbers = [1, [2, 3], [4, [5, 6]], 7];
console.log(sumNestedArray(nestedNumbers)); // 結果: 28

この例では、要素が配列である限り自分自身を呼び出し、数値であれば加算するという処理を繰り返すことで、どれだけ深い階層の配列でも正しく合計を求めることができます。ループ（for文）だけでこれを実現しようとすると、コードが非常に複雑になります。

注意点：スタックオーバーフロー ⚠️

再帰処理の最も注意すべき点はスタックオーバーフローです。関数を呼び出すたびに、その呼び出し情報がメモリ（コールスタック）に積まれていきます。再帰の階層が深くなりすぎると（例えば、factorial(20000) のように）、このメモリ領域が溢れてしまい、エラーでプログラムが停止します。

そのため、非常に大量の繰り返し処理が想定される場合は、for や while を使ったループ処理の方が安全でパフォーマンスが良いことがあります。

再帰は、コードを劇的にシンプルにし、可読性を高めることができる強力なツールですが、その仕組みと注意点を理解して適切に使うことが重要です。

GitHubで編集を提案

Discussion