Python再帰関数とは？初心者向け基礎解説と簡単な例

みなさん、「再帰関数」という言葉を聞いたことはありますか？

「関数が自分自身を呼び出すって何？」 「どんな時に使うの？」 「難しそうで理解できない...」

こんな疑問を持っている方も多いのではないでしょうか。

でも大丈夫です！ 再帰関数は、関数が自分自身を呼び出すプログラミング手法です。

この記事では、再帰関数の基本から実用的な使い方まで、初心者の方でも理解できるように詳しく解説します。

一緒に再帰関数をマスターしていきましょう！

再帰関数って何？

再帰関数とは、関数が自分自身を呼び出すプログラミング手法です。

複雑な問題を小さな問題に分けて解決できる、とても便利な方法です。

一番シンプルな例

まずは簡単な例から見てみましょう。

def simple_recursion(n):
    """シンプルな再帰関数の例"""
    
    # 基本ケース（再帰を止める条件）
    if n <= 0:
        return
    
    # 処理の実行
    print(f"カウント: {n}")
    
    # 再帰呼び出し（自分自身を呼び出す）
    simple_recursion(n - 1)

# 使用例
print("=== 基本的な再帰関数 ===")
simple_recursion(5)

実行結果：

カウント: 5 カウント: 4 カウント: 3 カウント: 2 カウント: 1

この例では、simple_recursion関数が自分自身を呼び出しています。

数字を1つずつ減らしながら、カウントダウンをしているんですね。

再帰関数の2つの要素

再帰関数には、必ず2つの要素が必要です。

def explain_recursion_structure():
    """再帰関数の構造説明"""
    
    print("=== 再帰関数の構造 ===")
    
    # 要素1: 基本ケース（Base Case）
    def base_case_example(n):
        if n <= 0:  # ← これが基本ケース
            return "終了"
        return f"処理中: {n}"
    
    # 要素2: 再帰ケース（Recursive Case）
    def recursive_case_example(n):
        if n <= 0:
            return "終了"
        
        # 現在の処理
        result = f"処理: {n}"
        
        # 再帰呼び出し（自分自身を呼び出す）
        next_result = recursive_case_example(n - 1)
        
        return f"{result} -> {next_result}"
    
    print("基本ケース例:", base_case_example(0))
    print("再帰ケース例:", recursive_case_example(3))

explain_recursion_structure()

要素1：基本ケース

• 再帰を止める条件
• これがないと無限ループになる

要素2：再帰ケース

• 自分自身を呼び出す部分
• 問題を小さくして渡す

どうやって動いているの？

再帰関数がどのように実行されるかを詳しく見てみましょう。

def trace_recursion(n, indent=0):
    """再帰関数の実行過程を追跡"""
    
    # インデントで階層を視覚化
    spaces = "  " * indent
    print(f"{spaces}→ trace_recursion({n}) 開始")
    
    # 基本ケース
    if n <= 0:
        print(f"{spaces}← 基本ケース到達: 0 を返す")
        return 0
    
    # 再帰呼び出し
    print(f"{spaces}  {n} + trace_recursion({n-1}) を計算")
    
    # 再帰的に関数を呼び出す
    result = n + trace_recursion(n - 1, indent + 1)
    
    print(f"{spaces}← trace_recursion({n}) 終了: {result} を返す")
    return result

# 実行例
print("=== 再帰関数の実行過程 ===")
final_result = trace_recursion(3)
print(f"
最終結果: {final_result}")

実行結果：

→ trace_recursion(3) 開始 3 + trace_recursion(2) を計算 → trace_recursion(2) 開始 2 + trace_recursion(1) を計算 → trace_recursion(1) 開始 1 + trace_recursion(0) を計算 → trace_recursion(0) 開始 ← 基本ケース到達: 0 を返す ← trace_recursion(1) 終了: 1 を返す ← trace_recursion(2) 終了: 3 を返す ← trace_recursion(3) 終了: 6 を返す 最終結果: 6

まるで積み木を積んで、また取り崩していくような感じですね。

階乗計算で再帰関数を理解する

階乗（factorial）は再帰関数の代表的な例です。

5! = 5 × 4 × 3 × 2 × 1 = 120 という計算ですね。

基本的な階乗計算

def factorial(n):
    """階乗を計算する再帰関数"""
    
    # 基本ケース
    if n <= 1:
        return 1
    
    # 再帰ケース
    return n * factorial(n - 1)

# 使用例
print("=== 階乗計算 ===")
numbers = [1, 3, 5, 7]

for num in numbers:
    result = factorial(num)
    print(f"{num}! = {result}")

実行結果：

1! = 1 3! = 6 5! = 120 7! = 5040

これはとてもシンプルですよね。

階乗の定義をそのままコードにしたような感じです。

計算過程を見てみる

階乗がどのように計算されるかを詳しく見てみましょう。

def factorial_with_steps(n):
    """階乗計算の過程を表示"""
    
    print(f"
=== {n}! の計算過程 ===")
    
    def factorial_inner(num, steps=[]):
        """内部の階乗計算（過程を記録）"""
        
        steps.append(num)
        
        if num <= 1:
            calculation = " × ".join(map(str, reversed(steps)))
            print(f"計算式: {calculation}")
            return 1
        
        return num * factorial_inner(num - 1, steps)
    
    result = factorial_inner(n)
    print(f"結果: {n}! = {result}")
    return result

# 使用例
factorial_with_steps(5)
factorial_with_steps(6)

実行結果：

=== 5! の計算過程 === 計算式: 1 × 2 × 3 × 4 × 5 結果: 5! = 120 === 6! の計算過程 === 計算式: 1 × 2 × 3 × 4 × 5 × 6 結果: 6! = 720

このように、再帰関数は数学的な定義をそのままコードにできるのが魅力です。

階乗の実用例

階乗は組み合わせ計算でも使われます。

def combination(n, r):
    """組み合わせ計算 nCr"""
    
    if r > n or r < 0:
        return 0
    
    if r == 0 or r == n:
        return 1
    
    # nCr = n! / (r! × (n-r)!)
    return factorial(n) // (factorial(r) * factorial(n - r))

def permutation(n, r):
    """順列計算 nPr"""
    
    if r > n or r < 0:
        return 0
    
    # nPr = n! / (n-r)!
    return factorial(n) // factorial(n - r)

# 使用例
print("
=== 組み合わせと順列 ===")
n, r = 5, 3

comb_result = combination(n, r)
perm_result = permutation(n, r)

print(f"{n}C{r} = {comb_result}")
print(f"{n}P{r} = {perm_result}")

# 実際の計算例
print(f"
{n}C{r} = {n}! / ({r}! × {n-r}!)")
print(f"    = {factorial(n)} / ({factorial(r)} × {factorial(n-r)})")
print(f"    = {factorial(n)} / {factorial(r) * factorial(n-r)}")
print(f"    = {comb_result}")

実行結果：

5C3 = 10 5P3 = 60 5C3 = 5! / (3! × 2!) = 120 / (6 × 2) = 120 / 12 = 10

階乗を使うことで、数学の計算がとても簡単になりますね。

フィボナッチ数列で再帰を深く理解する

フィボナッチ数列は、前の2つの数を足した数が次の数になる数列です。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... という並びですね。

基本的なフィボナッチ数列

def fibonacci(n):
    """フィボナッチ数列を計算する再帰関数"""
    
    # 基本ケース
    if n <= 1:
        return n
    
    # 再帰ケース
    return fibonacci(n - 1) + fibonacci(n - 2)

# 使用例
print("=== フィボナッチ数列 ===")
for i in range(10):
    result = fibonacci(i)
    print(f"F({i}) = {result}")

実行結果：

F(0) = 0 F(1) = 1 F(2) = 1 F(3) = 2 F(4) = 3 F(5) = 5 F(6) = 8 F(7) = 13 F(8) = 21 F(9) = 34

これも数学的な定義をそのままコードにした感じですね。

フィボナッチ数列の問題点

ただし、基本的な実装には問題があります。

同じ値を何度も計算してしまうんです。

def fibonacci_with_cache(n, cache={}):
    """メモ化を使ったフィボナッチ数列"""
    
    # キャッシュに結果があれば返す
    if n in cache:
        return cache[n]
    
    # 基本ケース
    if n <= 1:
        cache[n] = n
        return n
    
    # 再帰ケース（結果をキャッシュに保存）
    cache[n] = fibonacci_with_cache(n - 1, cache) + fibonacci_with_cache(n - 2, cache)
    return cache[n]

def fibonacci_comparison():
    """通常版とメモ化版の比較"""
    
    import time
    
    def measure_time(func, n):
        """実行時間を測定"""
        start = time.time()
        result = func(n)
        end = time.time()
        return result, end - start
    
    print("=== フィボナッチ数列の性能比較 ===")
    
    test_values = [10, 20, 30]
    
    for n in test_values:
        # 通常版
        result1, time1 = measure_time(fibonacci, n)
        
        # メモ化版
        result2, time2 = measure_time(fibonacci_with_cache, n)
        
        print(f"
F({n}) = {result1}")
        print(f"通常版: {time1:.6f}秒")
        print(f"メモ化版: {time2:.6f}秒")
        if time2 > 0:
            print(f"速度向上: {time1/time2:.1f}倍")

fibonacci_comparison()

「メモ化」という技術を使うことで、計算済みの結果を保存して高速化できます。

フィボナッチ数列の面白い性質

フィボナッチ数列には面白い性質があります。

def fibonacci_applications():
    """フィボナッチ数列の応用例"""
    
    print("=== フィボナッチ数列の応用 ===")
    
    # 黄金比の計算
    def golden_ratio_approximation(n):
        """フィボナッチ数列から黄金比を近似"""
        
        if n <= 1:
            return 1
        
        fib_n = fibonacci_with_cache(n)
        fib_n_minus_1 = fibonacci_with_cache(n - 1)
        
        return fib_n / fib_n_minus_1
    
    print("黄金比の近似:")
    for i in range(5, 21, 5):
        ratio = golden_ratio_approximation(i)
        print(f"F({i})/F({i-1}) = {ratio:.6f}")
    
    # 実際の黄金比
    import math
    actual_golden_ratio = (1 + math.sqrt(5)) / 2
    print(f"実際の黄金比: {actual_golden_ratio:.6f}")

fibonacci_applications()

実行結果：

黄金比の近似: F(5)/F(4) = 1.666667 F(10)/F(9) = 1.618182 F(15)/F(14) = 1.618037 F(20)/F(19) = 1.618034 実際の黄金比: 1.618034

フィボナッチ数列の比率は、黄金比に近づいていくんですね！

再帰関数を使う時の注意点

再帰関数はとても便利ですが、注意が必要な点もあります。

スタックオーバーフローに注意

def stack_overflow_demo():
    """スタックオーバーフローの例と対策"""
    
    import sys
    
    print("=== スタックオーバーフローの対策 ===")
    print(f"デフォルトの再帰限界: {sys.getrecursionlimit()}")
    
    # 安全な再帰関数
    def safe_factorial(n, max_depth=1000):
        """安全な階乗計算"""
        
        if n > max_depth:
            raise ValueError(f"値が大きすぎます（最大{max_depth}）")
        
        if n <= 1:
            return 1
        
        return n * safe_factorial(n - 1, max_depth)
    
    # 反復版での実装
    def iterative_factorial(n):
        """反復版階乗計算"""
        
        if n < 0:
            raise ValueError("0以上の整数を入力してください")
        
        result = 1
        for i in range(1, n + 1):
            result *= i
        
        return result
    
    # 性能比較
    test_values = [10, 100, 500]
    
    for n in test_values:
        try:
            rec_result = safe_factorial(n)
            iter_result = iterative_factorial(n)
            
            print(f"
{n}! の計算:")
            print(f"再帰版: 正常計算")
            print(f"反復版: 正常計算")
            print(f"結果一致: {rec_result == iter_result}")
            
        except ValueError as e:
            print(f"エラー: {e}")

stack_overflow_demo()

大きな値を扱う場合は、反復版を使う方が安全な場合もあります。

メモ化で性能を改善

よく使われるメモ化の実装方法を見てみましょう。

def memoization_examples():
    """メモ化の実装例"""
    
    print("=== メモ化による最適化 ===")
    
    # デコレーターを使った汎用メモ化
    def memoize(func):
        """メモ化デコレーター"""
        cache = {}
        
        def wrapper(*args):
            if args in cache:
                return cache[args]
            
            result = func(*args)
            cache[args] = result
            return result
        
        return wrapper
    
    # メモ化を適用したフィボナッチ
    @memoize
    def fibonacci_memoized(n):
        """メモ化されたフィボナッチ数列"""
        if n <= 1:
            return n
        return fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)
    
    # メモ化を適用した階乗
    @memoize
    def factorial_memoized(n):
        """メモ化された階乗計算"""
        if n <= 1:
            return 1
        return n * factorial_memoized(n - 1)
    
    # 使用例
    print("メモ化されたフィボナッチ:")
    for i in range(10):
        result = fibonacci_memoized(i)
        print(f"F({i}) = {result}")
    
    print("
メモ化された階乗:")
    for i in range(1, 8):
        result = factorial_memoized(i)
        print(f"{i}! = {result}")

memoization_examples()

デコレーターを使うと、簡単にメモ化を適用できます。

実用的な再帰関数の例

日常的なプログラミングでも再帰関数は活躍します。

リスト操作での再帰関数

def list_recursion_examples():
    """リスト操作での再帰関数"""
    
    print("=== リスト操作での再帰関数 ===")
    
    # リストの合計値を計算
    def sum_list(items):
        """リストの合計値を再帰的に計算"""
        if not items:
            return 0
        return items[0] + sum_list(items[1:])
    
    # リストの最大値を検索
    def max_list(items):
        """リストの最大値を再帰的に検索"""
        if len(items) == 1:
            return items[0]
        
        max_rest = max_list(items[1:])
        return items[0] if items[0] > max_rest else max_rest
    
    # リストを逆順にする
    def reverse_list(items):
        """リストを再帰的に逆順にする"""
        if len(items) <= 1:
            return items
        
        return reverse_list(items[1:]) + [items[0]]
    
    # フラットなリストにする
    def flatten_list(items):
        """ネストしたリストをフラットにする"""
        result = []
        
        for item in items:
            if isinstance(item, list):
                result.extend(flatten_list(item))
            else:
                result.append(item)
        
        return result
    
    # 使用例
    test_list = [1, 2, 3, 4, 5]
    nested_list = [1, [2, 3], [4, [5, 6]], 7]
    
    print(f"元のリスト: {test_list}")
    print(f"合計値: {sum_list(test_list)}")
    print(f"最大値: {max_list(test_list)}")
    print(f"逆順: {reverse_list(test_list)}")
    
    print(f"
ネストしたリスト: {nested_list}")
    print(f"フラット化: {flatten_list(nested_list)}")

list_recursion_examples()

実行結果：

元のリスト: [1, 2, 3, 4, 5] 合計値: 15 最大値: 5 逆順: [5, 4, 3, 2, 1] ネストしたリスト: [1, [2, 3], [4, [5, 6]], 7] フラット化: [1, 2, 3, 4, 5, 6, 7]

特にネストしたリストをフラット化する処理は、再帰関数の得意分野です。

文字列操作での再帰関数

def string_recursion_examples():
    """文字列操作での再帰関数"""
    
    print("=== 文字列操作での再帰関数 ===")
    
    # 文字列を逆順にする
    def reverse_string(text):
        """文字列を再帰的に逆順にする"""
        if len(text) <= 1:
            return text
        
        return reverse_string(text[1:]) + text[0]
    
    # 回文判定
    def is_palindrome(text):
        """回文かどうかを再帰的に判定"""
        # 空文字列または1文字は回文
        if len(text) <= 1:
            return True
        
        # 最初と最後の文字が同じかチェック
        if text[0] != text[-1]:
            return False
        
        # 中間部分を再帰的にチェック
        return is_palindrome(text[1:-1])
    
    # 文字のカウント
    def count_char(text, char):
        """特定の文字の個数を再帰的にカウント"""
        if not text:
            return 0
        
        count = 1 if text[0] == char else 0
        return count + count_char(text[1:], char)
    
    # 文字列の置換
    def replace_char(text, old_char, new_char):
        """文字を再帰的に置換"""
        if not text:
            return ""
        
        first_char = new_char if text[0] == old_char else text[0]
        return first_char + replace_char(text[1:], old_char, new_char)
    
    # 使用例
    test_strings = ["hello", "racecar", "level", "python"]
    
    for text in test_strings:
        print(f"
文字列: '{text}'")
        print(f"逆順: '{reverse_string(text)}'")
        print(f"回文: {is_palindrome(text)}")
        print(f"'l'の個数: {count_char(text, 'l')}")
        print(f"'l'→'L'置換: '{replace_char(text, 'l', 'L')}'")

string_recursion_examples()

実行結果：

文字列: 'hello' 逆順: 'olleh' 回文: False 'l'の個数: 2 'l'→'L'置換: 'heLLo' 文字列: 'racecar' 逆順: 'racecar' 回文: True 'l'の個数: 0 'l'→'L'置換: 'racecar'

回文判定なども、再帰関数で自然に表現できます。

再帰関数の設計のコツ

良い再帰関数を作るためのコツをまとめてみましょう。

def recursion_design_principles():
    """再帰関数の設計原則"""
    
    print("=== 再帰関数の設計原則 ===")
    
    # 原則1: 明確な基本ケース
    def good_base_case(n):
        """良い基本ケースの例"""
        # 明確で理解しやすい条件
        if n <= 0:
            return 0
        return n + good_base_case(n - 1)
    
    # 原則2: 問題のサイズを小さくする
    def good_problem_reduction(items):
        """問題を小さくする例"""
        # 空リストは基本ケース
        if not items:
            return 0
        
        # 問題のサイズを1つ減らす
        return items[0] + good_problem_reduction(items[1:])
    
    # 原則3: 入力値の検証
    def validated_recursion(n):
        """入力値を検証する再帰関数"""
        
        # 事前条件の確認
        if not isinstance(n, int):
            raise TypeError("整数を入力してください")
        
        if n < 0:
            raise ValueError("0以上の値を入力してください")
        
        # 基本ケース
        if n <= 1:
            return n
        
        # 再帰ケース
        return validated_recursion(n - 1) + validated_recursion(n - 2)
    
    # 使用例
    print("良い設計の例:")
    print(f"good_base_case(5): {good_base_case(5)}")
    print(f"good_problem_reduction([1,2,3,4]): {good_problem_reduction([1,2,3,4])}")
    
    try:
        print(f"validated_recursion(10): {validated_recursion(10)}")
    except (TypeError, ValueError) as e:
        print(f"エラー: {e}")

recursion_design_principles()

実行結果：

良い設計の例: good_base_case(5): 15 good_problem_reduction([1,2,3,4]): 10 validated_recursion(10): 55

設計のコツ：

1. 明確な基本ケースを設定する
2. 問題のサイズを確実に小さくする
3. 入力値を検証する
4. エラーハンドリングを忘れない

まとめ

Python再帰関数について、基本から実用例まで詳しく解説しました。

重要なポイント

再帰関数の基本：

• 関数が自分自身を呼び出す手法
• 基本ケースと再帰ケースが必要
• 複雑な問題を小さく分解して解決

よく使われる場面：

• 数学的な計算（階乗、フィボナッチ）
• リスト・文字列の処理
• ツリー構造の操作
• アルゴリズムの実装

注意すべき点：

• スタックオーバーフローのリスク
• 性能の問題（メモ化で改善）
• 基本ケースを忘れないこと

次のステップ

再帰関数をマスターするための学習順序：

1. 基本をしっかり理解：階乗とフィボナッチから始める
2. 実践で使ってみる：リスト・文字列処理で練習
3. 最適化を学ぶ：メモ化やエラーハンドリング
4. 応用に挑戦：ツリー構造やアルゴリズム

再帰関数は、考え方に慣れるまで少し時間がかかるかもしれません。 でも、一度理解できると、とても強力なプログラミング手法になります。

ぜひ実際にコードを書いて、再帰関数の面白さを体感してみてください！