再帰

関数が自分自身を呼び出す手法。

再帰
関数が自分自身を呼び出す手法。
基本ケース
再帰を終了する条件。
再帰ケース
関数が自分自身を呼び出す部分。
末尾再帰
再帰呼び出しが関数の最後の操作である再帰。
メモ化
計算結果をキャッシュして、再計算を避ける最適化手法。
スタックオーバーフロー
再帰が深すぎて、コールスタックがオーバーフローするエラー。
深さ
再帰の呼び出し回数。

再帰

マトリョーシカ

再帰は「マトリョーシカ」のようなもの。大きなマトリョーシカの中に、小さなマトリョーシカが入っていて、さらにその中に、さらに小さなマトリョーシカが入っています。一番小さなマトリョーシカを開けると、再帰が終了します。

なぜ再帰が必要か？

再帰は、関数が自分自身を呼び出す手法です。木構造の走査、フィボナッチ数列、階乗計算など、再帰的な問題を簡潔に解決できます。特に、問題の構造が再帰的である場合、再帰を使うことで、コードを簡潔に書けます。

いつ使うか？

  • 木構造を走査する場合
  • フィボナッチ数列を計算する場合
  • 階乗を計算する場合
  • 再帰的な問題を解決する場合

実践テクニック

基本ケースを明確にする

再帰の基本ケース（終了条件）を明確に定義することは重要です。基本ケースが正しく定義されていない場合、再帰が無限に続いて、スタックオーバーフローが発生します。

再帰ケースを簡潔にする

再帰ケースを簡潔に保つことで、コードの可読性を向上できます。再帰ケースが複雑すぎる場合、コードが理解しにくくなります。

スタックオーバーフローを回避する

再帰が深すぎる場合、スタックオーバーフローが発生します。これを回避するために、末尾再帰やメモ化などの最適化手法を使います。

末尾再帰を活用する

末尾再帰は、再帰呼び出しが関数の最後の操作である再帰です。末尾再帰は、コンパイラによって最適化され、スタックオーバーフローを回避できます。

メモ化を活用する

メモ化は、計算結果をキャッシュして、再計算を避ける最適化手法です。フィボナッチ数列など、同じ計算が繰り返される問題に有効です。Pythonの `@lru_cache` デコレータを使うことで、簡単にメモ化を実装できます。

Recursion Example
# 再帰の基本操作
def factorial(n):
    # 基本ケース
    if n <= 1:
        return 1
    # 再帰ケース
    return n * factorial(n - 1)


# 使用例
print(factorial(5))  # 120

基本構造

再帰の基本構造を確認する。

Basic Structure
# 再帰の基本操作
def factorial(n):
    # 基本ケース
    if n <= 1:
        return 1
    # 再帰ケース
    return n * factorial(n - 1)


# 使用例
print(factorial(5))  # 120

フィボナッチ数列

フィボナッチ数列の再帰的実装を確認する。

Fibonacci Sequence
# フィボナッチ数列の再帰
def fibonacci(n):
    # 基本ケース
    if n <= 1:
        return n
    # 再帰ケース
    return fibonacci(n - 1) + fibonacci(n - 2)


# 使用例
print(fibonacci(10))  # 55

末尾再帰

末尾再帰の実装を確認する。

Tail Recursion
# 末尾再帰の実装
def factorial_tail(n, accumulator=1):
    # 基本ケース
    if n <= 1:
        return accumulator
    # 再帰ケース（末尾再帰）
    return factorial_tail(n - 1, n * accumulator)


# 使用例
print(factorial_tail(5))  # 120

メモ化

メモ化の実装を確認する。

Memoization
# メモ化の実装
from functools import lru_cache


@lru_cache(maxsize=None)
def fibonacci(n):
    # 基本ケース
    if n <= 1:
        return n
    # 再帰ケース（メモ化）
    return fibonacci(n - 1) + fibonacci(n - 2)


# 使用例
print(fibonacci(10))  # 55

計算量

再帰の計算量を理解する。

手法 計算量 説明
再帰（フィボナッチ） O(2^n) 指数関数的に増加
メモ化（フィボナッチ） O(n) 線形的に増加
末尾再帰 O(n) 線形的に増加（最適化可能）

木構造の走査

木構造の走査（再帰）を確認する。

Tree Traversal
# 木構造の走査（再帰）
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def inorder_traversal(node):
    if node is None:
        return []
    # 左の子を走査
    left = inorder_traversal(node.left)
    # 親ノード
    current = [node.value]
    # 右の子を走査
    right = inorder_traversal(node.right)
    return left + current + right


# 使用例
root = Node(50)
root.left = Node(30)
root.right = Node(70)
root.left.left = Node(20)
root.left.right = Node(40)


print(inorder_traversal(root))  # [20, 30, 40, 50, 70]

合格ライン

☐ 再帰の基本構造を理解している
☐ 基本ケースと再帰ケースを区別できる
☐ 末尾再帰を理解している
☐ メモ化を理解している
☐ 再帰の計算量を理解している
☐ 再帰の使い分けができる

演習課題

課題1: 階乗の計算
階乗を計算する再帰関数を実装してください。
課題2: フィボナッチ数列
フィボナッチ数列を計算する再帰関数を実装してください。
課題3: 木構造の走査
木構造を走査する再帰関数を実装してください。

参考文献

この記事は以下の公的ガイドライン/標準に基づいています。