1. はじめに

エンジニアとして 3 年が経過しようとしている中、技術を使ってより高度な問題解決をしていくためには、フレームワークや言語に依存しない基礎となる知識が必要だと感じたため、CS を勉強し直しています。
その学習内容を備忘録として発信します。
今回は「再帰関数」についてです。

2. 話の進め方

本記事では、「再帰関数とは何か」、「再帰関数はなぜ必要なのか」、「再帰関数の使い方と注意点」という順番で解説を進めます。
尚、サンプルのコードには Ruby を使用します。

3. 再帰関数とは

再帰関数とは、自分自身を呼び出すことによって処理を繰り返す関数のことです。この「自分自身を呼び出す」という考え方を、コンピュータサイエンスでは「再帰的（recursive）」と表現します。

「再帰的（recursive）」という言葉は、ラテン語の “recurrere”（「繰り返し戻る」の意）に由来し、同じ構造を内包する構造を指します。これは、数学や哲学でも使われる概念で、「定義の中にその定義自身が現れる」という自己参照的な特徴を持ちます。

英語圏のコンピュータサイエンスの文献では、再帰関数は次のように定義されることが一般的です。

“A recursive function is a function that calls itself either directly or indirectly in order to solve a > problem by breaking it down into simpler sub-problems.”

（訳：「再帰関数とは、自分自身を直接または間接的に呼び出すことで、問題をより単純な部分問題に分割して解決する関数のことである。」）

このように、再帰関数は単なる自己呼び出しにとどまらず、「問題を部分的に解いて全体の解を導く」というアルゴリズム的な意義を持っています。

4. 再帰関数はなぜ必要か

4-1. コードの可読性という観点

再帰関数を使うと、複雑な繰り返し処理や分岐処理をシンプルで直感的な形で記述できます。たとえば、木構造や階層構造を扱う処理では、再帰によってコードの見通しが良くなります。

4-2. コードの保守性という観点

再帰は処理の本質的なロジックを簡潔に表現できるため、将来的な修正や拡張がしやすくなります。ループ処理で書かれた冗長なコードと比べて、意図が明確になり、バグの温床が減ります。

4-3. コンピュータのパフォーマンスという観点

場合によっては、再帰を利用することで計算量を抑えた効率的なアルゴリズムを実装できます（例：分割統治法）。ただし、関数呼び出しのコストがかかるため、常にパフォーマンスが向上するとは限りません。

5. 再帰関数の使い所

5-1. 階層構造を扱うとき

ツリー構造（例：ファイルシステム、組織図、HTML DOM など）を扱うときには、再帰関数が非常に適しています。ノードを辿って同じ処理を繰り返すような場面では、再帰を使うことで簡潔な実装が可能です。

5-2. 同じ処理を繰り返しながら、状態を変化させたいとき

たとえば、「ある数値を1ずつ減らしながら処理したい」「配列の先頭から順に処理をしたい」といった場面で、状態（引数）を変化させながら自己呼び出しする再帰は自然な形になります。

5-3. 問題を小さな部分問題に分解できるとき

ソートアルゴリズム（クイックソート、マージソート）や探索（分割統治、バックトラッキング）のように、全体の問題を部分的に分割して解決していくタイプの問題に再帰がよく使われます。

5-4. 繰り返し処理の中で条件分岐が多くなるとき

ループ処理で条件分岐が複雑になりすぎる場合、再帰によって処理を分解・整理することで、可読性の高いコードになります。特に状態遷移が明確な処理（例：パズル解法、迷路探索）で役立ちます。

6. 再帰関数の具体的な使い方と注意点

再帰関数を使うには、「終了条件（ベースケース）」と「再帰呼び出し（再帰ステップ）」の2つが必要です。以下は、階乗（factorial）の例です。

6-1. 基本的な使い方


def factorial(n)
  if n == 0 # 終了条件（ベースケース）
    return 1
  else
    return n * factorial(n - 1)  # 再帰呼び出し（再帰ステップ）
  end
end

factorial(3) を呼び出すと、

factorial(3) = 3 * factorial(2)
             = 3 * 2 * factorial(1)
             = 3 * 2 * 1 * factorial(0)
             = 3 * 2 * 1 * 1
             = 6

のように再帰的に処理が行われ、最終的な結果を導き出します。

6-2. 使うときの注意点

6-2-1. 終了条件を必ず設定すること

終了条件がないと、無限ループになり、スタックオーバーフロー（メモリの限界）を引き起こします。

6-2-2. スタックの深さに注意

言語によっては、関数呼び出しの深さに制限があります。深い再帰を多用する場合は、末尾再帰を使用したり、ループやスタック構造を使った非再帰的実装を検討しましょう。

6-2-3. パフォーマンスの最適化

同じ計算を何度も繰り返す再帰は非効率です。メモ化（結果のキャッシュ）や動的計画法を併用すると、計算効率を大きく改善できます。

7. まとめ

再帰関数は、自己参照を通じて複雑な問題をシンプルに解決する強力な手法です。特に、階層構造や繰り返し構造の問題に対して高い表現力を持ちます。ただし、使い方を誤るとパフォーマンスや安全性に悪影響があるため、終了条件と最適化を意識して使うことが重要です。