Python再帰関数の基本と使い方10選

はじめに

Pythonの再帰関数は、関数の中から同じ関数を呼び出し、問題を小さな単位へ分けて解く書き方です。階層データ、数列、探索、ソートのように「同じ形の処理が内側へ続く」場面では、forやwhileより構造を読み取りやすいコードになる場合があります。

ただし、再帰関数には停止条件、呼び出し回数、メモリ消費という注意点があります。そのため、基本を押さえたうえで、使い方、応用例、対策、カスタマイズをまとめて確認すると理解しやすくなるのが基本です。

再帰関数とは

結論から言えば、再帰関数は「停止条件」と「自分自身を呼ぶ処理」をセットで持つ関数です。停止条件がないと呼び出しが終わらないため、再帰関数の基本はifで終点を決め、残りの処理を小さな問題として同じ関数へ渡す形になります。

def countdown(n):
    if n <= 0:
        return "done"
    print(n)
    return countdown(n - 1)

print(countdown(3))

結果: 期待される出力は3、2、1、doneの順です。

このサンプルコードでは、n <= 0が停止条件、countdown(n - 1)が再帰呼び出しです。その条件に近づくようにnを減らしているため、呼び出しはいずれ終了します。

これをループで書くこともできます。一方で、ディレクトリの中にディレクトリがある、ツリーの子要素がさらに子要素を持つ、といった入れ子構造では、再帰関数のほうがデータ構造と処理の形を合わせやすいと言えるでしょう。

公式ドキュメントによれば、Pythonには再帰呼び出しの上限に関わるsys.getrecursionlimit()が用意されているのが目安です。詳しい仕様はPython公式ドキュメントのsysで確認できるのが基本です。

再帰関数の基本

再帰関数の基本は、base caseとrecursive caseを分けて読むことです。base caseは終わりを表し、recursive caseは答えを出すために少し小さな入力へ変換します。

そのため、サンプルコードを書く前に「何を受け取り、どの条件で止まり、次の呼び出しへ何を渡すか」を決めるのが基本です。この設計が曖昧だと、RecursionErrorや意図しない無限呼び出しにつながりますし、ここがポイントです。

def recursive_function(value):
    if value == 0:
        return 0
    return value + recursive_function(value - 1)

print(recursive_function(4))

結果: 期待される出力は10です。計算の内訳は4 + 3 + 2 + 1 + 0になります。

このときreturnは、下位の呼び出しから戻ってきた値を外側の呼び出しへ渡す役割を持ちます。初心者がつまずきやすいのは、呼び出しが深く進む方向と、値が戻って合成される方向を同時に追う点です。

具体的には、recursive_function(4)はすぐに答えを返さず、recursive_function(3)の答えを待ちますが、これは押さえたい点です。その待ちが0まで続き、停止条件に到達したあとで値が順に戻ってくる、と整理できるのが目安です。

再帰関数の使い方

再帰関数の使い方は、短いサンプルコードから始めると追いやすくなります。具体例としてファクトリアル、フィボナッチ、リスト探索、ディレクトリ探索を扱い、基本の形がどのように変わるかを確認します。

サンプルコード1：ファクトリアルの計算

ファクトリアルは、正の整数nから1までを掛け合わせる計算です。その定義自体がn * factorial(n - 1)という形を持つため、再帰関数の基本を学ぶ題材として使われますし、これが一つの目安です。

def factorial(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n in (0, 1):
        return 1
    return n * factorial(n - 1)

print(factorial(5))

結果: 期待される出力は120です。

このコードでは、0と1を停止条件にしています。一般的に0!は1なので、n in (0, 1)でまとめて扱うと入力範囲が明確になります。

ただし、負数を受け取った場合に終わらない設計は避ける必要があるのがポイントです。その対策としてraise ValueErrorを置き、関数の前提に合わない入力を早い段階で止めているのがポイントです。

サンプルコード2：フィボナッチ数列の生成

フィボナッチ数列は、0、1から始まり、後の項が直前の2項の和になる数列です。その定義は再帰関数で書きやすい一方、同じ値を何度も計算しやすい注意点があります。

def fibonacci(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(8):
    print(fibonacci(i))

結果: 期待される出力は0、1、1、2、3、5、8、13です。

これを見ると、fibonacci(n - 1)とfibonacci(n - 2)が枝分かれして呼ばれることが分かります。一方で、fibonacci(5)の内部ではfibonacci(3)などが何度も登場するため、大きなnではメモ化が有効な対策になります。

サンプルコード3：リストの要素を再帰的に探索する

リスト探索では、先頭の要素を確認し、見つからなければ残りの範囲へ進む形にできるのが一般的です。この使い方は、木構造やグラフ探索へ進む前の基本として理解しやすい応用例です。

def recursive_search(items, target, index=0):
    if index >= len(items):
        return False
    if items[index] == target:
        return True
    return recursive_search(items, target, index + 1)

print(recursive_search([1, 2, 3, 4, 5], 3))
print(recursive_search([1, 2, 3, 4, 5], 6))

結果: 期待される出力はTrue、Falseの順です。

このサンプルコードでは、items[1:]ではなくindexを進めています。スライスで新しいリストを作り続けないため、要素数が増えた場合の余分なコピーを避けられます。

実装パターンとしてよく見るのは、探索済みの位置を引数で渡す書き方です。ただし、単純な一次元リストであればtarget in itemsのほうが短く、再帰関数は学習目的や階層探索の前段として使うのが現実的でしょう。

サンプルコード4：ディレクトリの再帰的な探索

ディレクトリ探索は、フォルダの中にフォルダがある入れ子構造です。そのため、再帰関数の使い方をファイルシステムへ広げる応用例として扱えますが、覚えておくと役立つでしょう。

from pathlib import Path

def walk_files(path):
    for child in Path(path).iterdir():
        if child.is_dir():
            walk_files(child)
        else:
            print(child)

walk_files("sample_dir")

結果: sample_dirが存在し、配下にファイルがある場合、期待される表示は各ファイルのパスです。

このときPath.iterdir()で直下の要素を取り出し、is_dir()が真なら同じwalk_filesへ渡します。ただし、存在しないパス、権限のないディレクトリ、シンボリックリンクの循環には注意点があります。

一般に、実用目的ならPath.rglob()やos.walk()も候補になるのが現実的です。再帰関数で自作する場合は、例外処理と探索対象の制限を加える対策を検討するとよいでしょう。

再帰関数の応用例

再帰関数の応用例では、同じ構造を単に繰り返すだけでなく、計算済みの値を再利用したり、候補を枝刈りしたりするのが一般的です。基本の停止条件を保ったまま、状態やキャッシュを加えるのが発展的な使い方です。

公式ドキュメントによれば、functools.lru_cacheは関数呼び出しの結果を保存するデコレータです。詳しい仕様はPython公式ドキュメントのfunctoolsで確認できます。

サンプルコード5：メモ化を用いた高速化

フィボナッチ数列のように同じ引数で何度も呼ばれる再帰関数では、メモ化が代表的な対策になると整理できます。Pythonでは辞書で自作する方法と、@lru_cacheを使う方法があるのが現実的です。

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 0:
        raise ValueError("n must be non-negative")
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))
print(fib.cache_info())

結果: 期待される出力の先頭は55です。cache_info()ではヒット数やミス数などのキャッシュ情報が表示されます。

このサンプルコードでは、maxsize=Noneによりキャッシュの上限を設けていません。一方で、長時間動くプログラムではメモリ使用量が増えるため、maxsize=128のように上限を決めるカスタマイズも候補になると理解できます。

サンプルコード6：再帰を使ったバックトラック法

バックトラック法は、候補を選び、条件に合わなければ戻って別の候補を試す探索方法です。N-クイーン問題では、行ごとにクイーンの列を選び、列と対角線の衝突を避けながら進めますし、ここがポイントです。

def solve_n_queens(n):
    solutions = []

    def can_place(row, col, queens):
        for r, c in enumerate(queens):
            if c == col or abs(row - r) == abs(col - c):
                return False
        return True

    def place(row, queens):
        if row == n:
            solutions.append(queens[:])
            return
        for col in range(n):
            if can_place(row, col, queens):
                queens.append(col)
                place(row + 1, queens)
                queens.pop()

    place(0, [])
    return solutions

print(solve_n_queens(4))

結果: 期待される出力は[[1, 3, 0, 2], [2, 0, 3, 1]]です。

このときqueens.append(col)で候補を追加し、探索後にqueens.pop()で状態を戻します。その戻す処理がないと、別の分岐へ前の候補が残り、正しい探索になりません。

ただし、バックトラック法は候補数が増えるほど計算量が膨らみます。その対策として、can_placeで早めに不可能な配置を除外し、探索する分岐を減らすのが基本です。

サンプルコード7：再帰を使った動的計画法

動的計画法は、部分問題の答えを保存しながら全体の答えを組み立てる考え方です。ナップサック問題では、品物を選ぶ場合と選ばない場合を比較し、容量ごとの最大価値を求めますし、ここを基本と考えるとよいでしょう。

from functools import lru_cache

def knapsack(capacity, weights, values):
    @lru_cache(maxsize=None)
    def choose(index, remaining):
        if index == len(weights) or remaining == 0:
            return 0
        if weights[index] > remaining:
            return choose(index + 1, remaining)
        take = values[index] + choose(index + 1, remaining - weights[index])
        skip = choose(index + 1, remaining)
        return max(take, skip)

    return choose(0, capacity)

print(knapsack(50, (10, 20, 30), (60, 100, 120)))

結果: 期待される出力は220です。

このサンプルコードでは、choose(index, remaining)が「何番目の品物から見るか」と「残り容量」を状態として持ちます。状態が同じなら答えも同じなので、@lru_cacheで再計算を抑えています。

サンプルコード8：ツリー構造の深さ優先探索

ツリー構造は、根から子、子から孫へ同じ形が続くデータです。そのため、深さ優先探索は再帰関数の応用例として自然に書けると覚えるとよいでしょう。

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def preorder(node):
    if node is None:
        return []
    return [node.data] + preorder(node.left) + preorder(node.right)

root = Node(1, Node(2, Node(4), Node(5)), Node(3))
print(preorder(root))

結果: 期待される出力は[1, 2, 4, 5, 3]です。

このコードでは、node is Noneが停止条件です。前順探索なので、現在のdataを先にリストへ入れ、左の部分木、右の部分木の順に結果を結合します。

サンプルコード9：再帰を使った分割統治法

分割統治法は、大きな問題を分け、分けた結果を統合して答えを作る方法です。最大値探索では、範囲を左右に分け、それぞれの最大値を比べます。

def find_max(nums, left, right):
    if left == right:
        return nums[left]
    mid = (left + right) // 2
    left_max = find_max(nums, left, mid)
    right_max = find_max(nums, mid + 1, right)
    return max(left_max, right_max)

nums = [1, 3, 5, 7, 6, 4, 2]
print(find_max(nums, 0, len(nums) - 1))

結果: 期待される出力は7です。

この使い方では、left == rightになったときに要素が一つだけになり、そこで値を返します。ただし、単に最大値を求めるだけならmax(nums)が標準的であり、分割統治の学習用サンプルコードとして読むのが自然です。

サンプルコード10：マージソートの実装

マージソートは、分割統治法をソートへ適用した代表的なアルゴリズムです。リストを半分に分け、左右を並べ替え、最後に小さい順へ統合します。

def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([6, 4, 8, 9, 2, 1, 7, 5, 3]))

結果: 期待される出力は[1, 2, 3, 4, 5, 6, 7, 8, 9]です。

この実装では、len(nums) <= 1が停止条件です。一方で、nums[:mid]やnums[mid:]は新しいリストを作るため、追加メモリが必要になります。

再帰関数の注意点と対策

再帰関数の注意点は、停止条件の漏れ、再帰の深さ、重複計算、共有状態の扱いに集約できます。対策を入れずに大きな入力へ適用すると、RecursionErrorやメモリ消費の増加につながるかもしれません。

そのため、実装前に「最大で何回呼ばれるか」「同じ引数が何度も出るか」「途中で状態を変更するか」を確認すると考えられますが、これは押さえたい点です。こうした確認は、再帰関数の使い方を安全側へ寄せる基本になります。

def limited_recursion(n, max_depth=5):
    if n > max_depth:
        raise ValueError(f"depth exceeded: {max_depth}")
    print(f"depth: {n}")
    return limited_recursion(n + 1, max_depth)

try:
    limited_recursion(0)
except ValueError as error:
    print(error)

結果: 期待される出力はdepth: 0からdepth: 5までの表示後、depth exceeded: 5です。

この対策では、Pythonの再帰上限へ達する前に、アプリケーション側の条件で処理を止めています。ただし、単にsys.setrecursionlimit()で上限を上げる方法は、根本原因を隠す場合があります。

一般に、入力が深くなる可能性が高い処理では、再帰からstackを使った反復処理へ切り替える判断も必要です。一方で、階層の深さが限定され、停止条件が明確なら、再帰関数は読みやすい選択肢になると言えるでしょう。

def fib_with_memo(n, memo=None):
    if memo is None:
        memo = {0: 0, 1: 1}
    if n not in memo:
        memo[n] = fib_with_memo(n - 1, memo) + fib_with_memo(n - 2, memo)
    return memo[n]

print(fib_with_memo(10))

結果: 期待される出力は55です。

このコードでは、memo=Noneから関数内で辞書を作っています。デフォルト引数に直接{}を書くと呼び出し間で状態が共有されるため、意図しない値の残存を避けるカスタマイズとして有効です。

初心者がつまずきやすいのは、見た目の短さだけで再帰関数を選ぶことです。短いコードでも計算量が大きい場合があるため、メモ化、反復処理、標準ライブラリの利用を比較する対策が必要になります。

再帰関数のカスタマイズ方法

再帰関数のカスタマイズでは、戻り値、引数、停止条件、内部状態を変えますし、ここがポイントです。基本の形を保ったまま、リストの平坦化、深さ制限、条件付き抽出のような使い方へ広げられますし、これが一つの目安です。

具体的には、ネストされたリストを平坦化する処理では、要素がリストなら再帰し、リストでなければ結果へ追加します。この分岐は、階層データの処理でよく見る応用例です。

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

nested = [1, [2, 3], [4, [5, 6], 7]]
print(flatten(nested))

結果: 期待される出力は[1, 2, 3, 4, 5, 6, 7]です。

このサンプルコードでは、isinstance(item, list)で入れ子を判定しています。ただし、tupleも対象にしたい場合は、isinstance(item, (list, tuple))のように条件を広げるカスタマイズができます。

def flatten_selected(items, allowed_types=(int, float)):
    result = []
    for item in items:
        if isinstance(item, (list, tuple)):
            result.extend(flatten_selected(item, allowed_types))
        elif isinstance(item, allowed_types):
            result.append(item)
    return result

nested = [1, "skip", (2, [3.5, "x"]), [4]]
print(flatten_selected(nested))

結果: 期待される出力は[1, 2, 3.5, 4]です。

このカスタマイズでは、allowed_typesで取り出す型を切り替えています。そのため、同じ再帰関数でも、数値だけを集める、文字列だけを集める、といった使い方へ調整できます。

ただし、複雑なカスタマイズを入れすぎると、停止条件と戻り値の意味が読みにくくなるのが基本です。関数名、引数名、戻り値の型をそろえ、必要なら処理を小さな関数へ分けるのが基本です。

まとめ

Pythonの再帰関数は、停止条件と再帰呼び出しを組み合わせ、同じ形の小さな問題へ分解する書き方です。ファクトリアルやフィボナッチのような基本から、探索、分割統治、マージソートの応用例まで、共通して「終わる条件」と「次に渡す値」が読みどころになると整理できます。

その一方で、再帰の深さ、重複計算、メモリ消費には注意点があります。対策として、入力検証、メモ化、深さ制限、反復処理への切り替え、標準ライブラリの利用を比較すると、再帰関数の使い方を現実的に選べますが、これは押さえたい点です。

カスタマイズでは、戻り値を合成するか、引数で状態を渡すかによって読みやすさが変わります。サンプルコードを写すだけでなく、停止条件を変えた場合に何が起こるかを追うと、再帰関数の基本と応用例を結び付けて理解できると理解できます。

※本記事は実在のエンジニア複数名で構成される Japanシーモア編集部が、AI支援を活用して作成・校正・公開しています。

関連記事

• Python初心者のための完全ガイド！アプリ化の10ステップ
• Pythonで実現！ウィンドウ操作の自動化15選
• Pythonで折れ線グラフ作成の完全ガイド10選
• 初心者必見！Pythonで表を操作するための7つの詳細ガイド
• Pythonで改行あり・なしを制御する方法と応用例10選