Python再帰関数の使い方を徹底解説！初心者でもわかる基本から応用まで
Pythonプログラミングを学ぶ上で避けて通れないのが「再帰関数」です。一見難しそうに見える再帰関数ですが、仕組みを理解すれば非常に強力な武器になります。この記事では、Python初心者でも理解できるよう、再帰関数の基本概念から実践的な応用例まで、豊富なサンプルコードとともに徹底解説します。
再帰関数とは？基本概念を理解しよう
**再帰関数（Recursive Function）**とは、関数の中で自分自身を呼び出す関数のことです。数学的な定義や繰り返し処理を簡潔に表現できる強力な手法です。
再帰関数の基本構造
すべての再帰関数には以下の2つの要素が必要です：
- ベースケース（終了条件）：再帰を止める条件
- 再帰ケース：自分自身を呼び出す部分
def recursive_function(n):
# ベースケース（終了条件）
if n <= 0:
return "終了"
# 再帰ケース
return recursive_function(n - 1)
最も簡単な再帰関数の例：カウントダウン
def countdown(n):
if n <= 0:
print("終了！")
else:
print(n)
countdown(n - 1)
countdown(5)
# 出力: 5, 4, 3, 2, 1, 終了！
この例では：
- ベースケース：
n <= 0で再帰を終了 - 再帰ケース：
n-1で自分自身を呼び出し
フィボナッチ数列：再帰の代表例
フィボナッチ数列は再帰関数の典型的な例です。
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # 出力: 13
フィボナッチ数列の動作説明
fibonacci(4)
├── fibonacci(3)
│ ├── fibonacci(2)
│ │ ├── fibonacci(1) → 1
│ │ └── fibonacci(0) → 0
│ └── fibonacci(1) → 1
└── fibonacci(2)
├── fibonacci(1) → 1
└── fibonacci(0) → 0
階乗計算：数学的な再帰の応用
階乗（n!）も再帰で簡潔に表現できます。
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5)) # 出力: 120 (5×4×3×2×1)
リストの合計値：実用的な再帰例
def sum_list(lst):
if not lst:
return 0
return lst[0] + sum_list(lst[1:])
numbers = [1, 2, 3, 4, 5]
print(sum_list(numbers)) # 出力: 15
文字列の逆順：再帰で文字列操作
def reverse_string(s):
if len(s) <= 1:
return s
return s[-1] + reverse_string(s[:-1])
print(reverse_string("Python")) # 出力: nohtyP
ディレクトリ探索：実用的な再帰応用
import os
def find_files(path, extension):
files = []
for item in os.listdir(path):
item_path = os.path.join(path, item)
if os.path.isdir(item_path):
files.extend(find_files(item_path, extension))
elif item.endswith(extension):
files.append(item_path)
return files
# 使用例
# python_files = find_files("/my/project", ".py")
二分探索：効率的な検索アルゴリズム
def binary_search(arr, target, left=0, right=None):
if right is None:
right = len(arr) - 1
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, left, mid - 1)
else:
return binary_search(arr, target, mid + 1, right)
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7)) # 出力: 3
ハノイの塔：古典的な再帰問題
def hanoi(n, start, goal, aux):
if n == 1:
print(f"円盤1を{start}から{goal}へ移動")
else:
hanoi(n-1, start, aux, goal)
print(f"円盤{n}を{start}から{goal}へ移動")
hanoi(n-1, aux, goal, start)
hanoi(3, 'A', 'C', 'B')
再帰関数のメリットとデメリット
メリット
コードの簡潔性
- 複雑な問題を簡単に表現
- 数学的定義に忠実な実装
- 可読性の向上
問題の自然な表現
- 木構造の処理
- 分割統治法
- 数学的な漸化式
デメリット
パフォーマンスの問題
- 関数呼び出しのオーバーヘッド
- 重複計算の発生
- メモリ使用量の増加
スタックオーバーフローのリスク
# 危険な例：無限再帰
def infinite_recursion(n):
return infinite_recursion(n + 1) # 終了条件なし
再帰の最適化テクニック
メモ化（Memoization）
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
print(fibonacci_memo(50)) # 高速計算
末尾再帰の活用
def factorial_tail(n, acc=1):
if n <= 1:
return acc
return factorial_tail(n - 1, acc * n)
print(factorial_tail(5)) # 出力: 120
再帰 vs 反復処理：どちらを選ぶべき？
再帰が適している場面
- 木構造やグラフの探索
- 分割統治法のアルゴリズム
- 数学的な漸化式の実装
- 問題が自己相似性を持つ場合
# 再帰版：直感的
def power(base, exp):
if exp == 0:
return 1
return base * power(base, exp - 1)
反復処理が適している場面
- 単純な繰り返し処理
- パフォーマンスが重要な場合
- メモリ使用量を抑えたい場合
# 反復版：効率的
def power_iterative(base, exp):
result = 1
for _ in range(exp):
result *= base
return result
再帰関数のデバッグテクニック
トレース出力の活用
def fibonacci_debug(n, depth=0):
indent = " " * depth
print(f"{indent}fibonacci({n}) 開始")
if n <= 1:
print(f"{indent}fibonacci({n}) → {n}")
return n
result = fibonacci_debug(n-1, depth+1) + fibonacci_debug(n-2, depth+1)
print(f"{indent}fibonacci({n}) → {result}")
return result
fibonacci_debug(4)
再帰の深さ制限
import sys
# 再帰の深さ制限を設定
sys.setrecursionlimit(1000)
def deep_recursion(n):
if n <= 0:
return 0
return 1 + deep_recursion(n - 1)
実践的な再帰関数の応用例
JSON解析
def flatten_json(data):
result = {}
def _flatten(obj, parent_key=''):
if isinstance(obj, dict):
for k, v in obj.items():
new_key = f"{parent_key}.{k}" if parent_key else k
_flatten(v, new_key)
else:
result[parent_key] = obj
_flatten(data)
return result
data = {"user": {"name": "Alice", "age": 30}}
print(flatten_json(data)) # {'user.name': 'Alice', 'user.age': 30}
ツリー構造の処理
class TreeNode:
def __init__(self, val=0):
self.val = val
self.children = []
def tree_sum(node):
if not node:
return 0
return node.val + sum(tree_sum(child) for child in node.children)
よくある間違いと対処法
終了条件の設定ミス
# 間違い：終了条件なし
def bad_countdown(n):
print(n)
bad_countdown(n - 1) # 無限再帰
# 正しい例
def good_countdown(n):
if n <= 0: # 終了条件を忘れずに
return
print(n)
good_countdown(n - 1)
重複計算の対策
# 非効率：重複計算あり
def fibonacci_slow(n):
if n <= 1:
return n
return fibonacci_slow(n-1) + fibonacci_slow(n-2)
# 効率的：メモ化使用
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_fast(n):
if n <= 1:
return n
return fibonacci_fast(n-1) + fibonacci_fast(n-2)
再帰関数の学習ロードマップ
初級レベル
-
基本概念の理解
- ベースケースと再帰ケース
- 簡単なカウントダウン関数
-
数学的な例
- 階乗計算
- フィボナッチ数列
- べき乗計算
中級レベル
-
データ構造の処理
- リストの操作
- 文字列の処理
- 辞書の探索
-
アルゴリズムへの応用
- 二分探索
- クイックソート
- マージソート
上級レベル
-
実践的な応用
- ファイルシステムの探索
- 木構造の処理
- グラフアルゴリズム
-
最適化テクニック
- メモ化
- 末尾再帰
- 動的プログラミング
まとめ
Python再帰関数は、適切に使用すれば非常に強力なツールです。重要なポイントをまとめると：
再帰関数の基本
- 必ずベースケース（終了条件）を設定
- 自分自身を呼び出す再帰ケースを定義
- 問題を小さな部分問題に分割して解決
効果的な使用場面
- 木構造やグラフの処理
- 数学的な漸化式の実装
- 分割統治法のアルゴリズム
- 問題が自己相似性を持つ場合
注意すべきポイント
- スタックオーバーフローの回避
- パフォーマンスの考慮
- メモ化による最適化
再帰関数は最初は理解が難しいかもしれませんが、小さな例から始めて段階的に複雑な問題に取り組むことで、必ずマスターできます。実際にコードを書いて動作を確認しながら学習を進めることをおすすめします。
再帰関数を理解することで、Pythonプログラミングのスキルが大きく向上し、より複雑な問題も効率的に解決できるようになるでしょう。
■プロンプトだけでオリジナルアプリを開発・公開してみた！！
■AI時代の第一歩！「AI駆動開発コース」はじめました！
テックジム東京本校で先行開始。
■テックジム東京本校
「武田塾」のプログラミング版といえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
より早く、より安く、しかも対面型のプログラミングスクールです。
＜短期講習＞5日で5万円の「Pythonミニキャンプ」開催中。
＜月1開催＞放送作家による映像ディレクター養成講座
＜オンライン無料＞ゼロから始めるPython爆速講座
