Zenn
👻

[初心者向け] 再帰関数とは？

2023/04/19に公開
Python
アルゴリズム
tech

再帰関数の概要

再帰関数とは、自分自身を呼び出す関数のことを指します。再帰関数は、問題を繰り返し処理することで解決する場合に非常に有用です。一般的に、再帰関数は次の2つの要素が必要です。

  1. ベースケース (base case)：再帰を終了させるための条件。再帰が無限に続かないように、ある条件を満たしたら再帰を終了することが重要です。
  2. 再帰ステップ (recursive step)：自分自身を呼び出す部分で、問題を分割して処理します。

以下に、Pythonで記述された再帰関数の例を示します。

階乗を計算する再帰関数

def factorial(n: int) -> int:
    if n == 0:  # ベースケース
        return 1
    else:
        return n * factorial(n - 1)  # 再帰ステップ

上記の関数は、整数nの階乗を計算する再帰関数です。ベースケースとしてn == 0の場合、1を返します。再帰ステップでは、nをn-1の階乗と掛け合わせることで、nの階乗を計算しています。

再帰関数の利点と欠点

再帰関数は、問題を簡潔に記述できることが利点です。しかし、再帰関数には以下の欠点もあります。

  • スタックオーバーフロー：再帰の深さが深くなると、コンピュータのメモリ（スタック）を使い果たしてしまうことがあります。これを防ぐために、再帰の代わりにループを使うことが推奨される場合があります。
  • 実行速度：再帰関数はループに比べて実行速度が遅くなることがあります。ただし、再帰関数の実行速度を改善する方法も存在します（例：メモ化）。

再帰関数の実践的な使い方

再帰関数は、以下のような問題解決に適しています。

  • 木構造の探索（ディレクトリ構造やHTMLのDOMなど）
  • 数学的な問題（フィボナッチ数列やハノイの塔など）
  • 組み合わせや順列の生成
  • バックトラッキングアルゴリズム（パズルやゲームの解決策を見つける際に使用）

以下では、再帰関数の実践的な使い方をいくつかの例を通して説明します。

木構造の探索

再帰関数は、木構造を探索する際に非常に役立ちます。以下に、ディレクトリ構造を再帰的に探索し、ファイルの一覧を表示する例を示します。

import os

def list_files_recursive(path: str, depth: int = 0) -> None:
    for entry in os.listdir(path):
        entry_path = os.path.join(path, entry)

        if os.path.isfile(entry_path):
            print(" " * depth + entry)
        elif os.path.isdir(entry_path):
            print(" " * depth + entry + "/")
            list_files_recursive(entry_path, depth + 2)

この関数は、指定されたディレクトリからファイルとサブディレクトリを再帰的に探索し、その名前をインデントを付けて表示します。

フィボナッチ数列

フィボナッチ数列は、再帰関数を使用して簡単に計算できます。以下に、フィボナッチ数列を再帰関数で計算する例を示します。

def fibonacci(n: int) -> int:
    if n == 0:  # ベースケース
        return 0
    elif n == 1:  # ベースケース
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 再帰ステップ

ただし、上記の実装は効率が悪いため、実際に使用する際にはメモ化を行うことが推奨されます。以下に、メモ化を使用したフィボナッチ数列の計算例を示します。

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_memoized(n: int) -> int:
    if n == 0:  # ベースケース
        return 0
    elif n == 1:  # ベースケース
        return 1
    else:
        return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)  # 再帰ステップ

バックトラッキング

バックトラッキングは、解空間を探索して解決策を見つけるアルゴリズムです。再帰関数は、バックトラッキングアルゴリズムの実装に適しています。以下に、ナップサック問題を解くバックトラッキングの例を示します。

def knapsack_recursive(items: list, capacity: int, index: int = 0) -> int:
    if index == len(items) or capacity == 0:  # ベースケース
        return 0
    item_weight, item_value = items[index]

    if item_weight > capacity:  # 現在のアイテムがナップサックに入らない場合
        return knapsack_recursive(items, capacity, index + 1)
    else:
        # 現在のアイテムをナップサックに入れる場合
        take_item = item_value + knapsack_recursive(items, capacity - item_weight, index + 1)
        # 現在のアイテムをナップサックに入れない場合
        leave_item = knapsack_recursive(items, capacity, index + 1)

        return max(take_item, leave_item)  # 最大値を返す

# テスト用データ
items = [(2, 6), (2, 10), (3, 12), (1, 1)]
capacity = 5

result = knapsack_recursive(items, capacity)
print(f"Maximum value: {result}")

この関数は、ナップサック問題を解決するために、アイテムのリストとナップサックの容量を再帰的に処理します。再帰ステップでは、アイテムをナップサックに入れる場合と入れない場合の両方を考慮して、最大の価値を見つけます。

これらの例からわかるように、再帰関数はさまざまな問題解決に適した方法で、状況に応じて使用することが重要です。ただし、再帰関数の欠点も理解し、適切な対策を講じることが大切です。

二分探索

再帰関数を使用して二分探索を実装することができます。二分探索は、ソートされたリストに対して効率的に要素を探索するアルゴリズムです。

def binary_search_recursive(arr: list, target: int, low: int, high: int) -> int:
    if low > high:  # ベースケース: 見つからなかった場合
        return -1

    mid = (low + high) // 2
    if arr[mid] == target:  # ベースケース: 見つかった場合
        return mid
    elif arr[mid] > target:  # 再帰ステップ: 左側を探索
        return binary_search_recursive(arr, target, low, mid - 1)
    else:  # 再帰ステップ: 右側を探索
        return binary_search_recursive(arr, target, mid + 1, high)

# テスト用データ
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 6

result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Target found at index: {result}")

この関数は、ソートされたリスト arr 内で target を探索します。再帰ステップでは、リストの中央要素が目標値よりも大きいか小さいかに応じて、リストの左側または右側を探索しています。

再帰関数の使用に関する注意事項

再帰関数を使用する際には、以下の点に注意することが重要です。

  1. 再帰の深さに注意する: 再帰関数はメモリを大量に消費することがあり、スタックオーバーフローを引き起こす可能性があります。再帰の深さが大きい場合は、ループを使用して解決することを検討してください。
  2. 効率を向上させる方法を検討する: 再帰関数の実行速度が遅い場合は、メモ化などのテクニックを使用して効率を向上させることができます。
  3. クリーンなコードを書く: 再帰関数は、適切に実装された場合にコードが簡潔で読みやすくなりますが、適切に実装されていない場合は、コードが複雑で理解しにくくなることがあります。再帰関数を使用する際は、コードが簡潔で理解しやすいことを確認してください。

以上の例と注意事項を参照にしながら、再帰関数を効果的に使用してプログラムを書くことができます。再帰関数は、適切な問題設定に対して強力なツールとなりますが、その利点と欠点を理解し、状況に応じて適切に使用することが重要です。

深さ優先探索 (DFS)

深さ優先探索（DFS）は、グラフや木構造の探索に使用されるアルゴリズムで、再帰関数を使って実装できます。以下に、グラフの深さ優先探索を再帰関数で実装した例を示します。

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u: int, v: int) -> None:
        self.graph[u].append(v)

    def dfs_recursive(self, v: int, visited: set) -> None:
        visited.add(v)
        print(v, end=' ')

        for i in self.graph[v]:
            if i not in visited:
                self.dfs_recursive(i, visited)

# テスト用データ
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

visited = set()
g.dfs_recursive(2, visited)

この例では、Graph クラスに深さ優先探索を実装しています。dfs_recursive メソッドは、開始頂点と未訪問頂点のセットを引数として受け取り、頂点を訪問した順序で出力します。

再帰関数を利用した深さ優先探索は、木構造やグラフ構造を効率的に探索することができますが、同様に再帰の深さに注意する必要があります。

まとめ

再帰関数は、問題をシンプルに表現できる場合があり、多くのアルゴリズムやデータ構造に適用できます。しかし、再帰関数を使用する際には、パフォーマンスやメモリ使用量に注意する必要があります。適切な状況で再帰関数を使用し、コードの可読性や効率を向上させることができます。

Discussion