再帰と反復のトレードオフ
再帰的な階乗とFibonacciを反復ループに変換し、Pythonの再帰上限やスタックサイズによって反復が適する場合を説明します。
「再帰と反復のトレードオフ」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
再帰と反復の双対性
再帰で記述できるすべてのアルゴリズムは反復でも記述でき、その逆も同様です。再帰版は多くの場合、問題の数学的定義をより忠実に表します。一方、反復版ではメモリを明示的に制御でき、スタックオーバーフローのリスクを回避できます。どちらを選ぶかは、可読性、深度の制限、性能要件に基づいて判断する実用的な選択です。
面接では、両方のバージョンを示してトレードオフを説明できると、十分な理解を示す強いアピールになります。
階乗：再帰と反復
階乗は典型的な例です。再帰版は、n! = n × (n-1)! という数学的定義を直接コード化します。n 個の戻り値を保留するため、スタック領域の空間計算量は O(n) です。反復版は1から n までループし、空間計算量は O(1) です。n = 1000 では再帰版は Python のデフォルト制限に達しますが、反復版は任意に大きな n を処理できます。
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)フィボナッチ：指数時間と線形時間
素朴な再帰版フィボナッチの時間計算量は O(2^n) で、大きな n に対しては非常に低速です。反復版は時間計算量が O(n)、空間計算量が O(1) です。メモ化した再帰（次のレッスンで扱います）も時間計算量は O(n) ですが、メモ辞書と O(n) のスタックのため、空間計算量は O(n) です。フィボナッチでは、すべての指標において反復アプローチが最適です。n = 50 の場合、素朴な再帰には数秒かかりますが、反復処理なら数マイクロ秒です。
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large n木の走査：再帰と反復
再帰による木の走査は、木の構造と再帰の仕組みが自然に対応するため、すっきり記述できます。しかし、極端に偏った木（実質的に連結リスト）の場合、再帰の深さは木の高さと等しく O(n) になるため、スタックオーバーフローの危険があります。明示的なスタックを使う反復版には深さの上限がなく、コールスタックではなくヒープ上でスタックのサイズを拡張できます。
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]マージソート：再帰と反復（ボトムアップ）
マージソートは本質的に再帰的です（分割、再帰、マージ）。反復的なボトムアップマージソートでは、再帰を完全に避けます。まずサイズ 1 の部分配列から始め、隣接するペアをマージしてサイズ 2 の部分配列を作り、次にサイズ 4 へ進むというように、各パスで部分配列のサイズを 2 倍にします。ボトムアップマージソートの時間計算量は O(n log n)、空間計算量は O(n)（マージ用バッファ）、スタック空間は O(1) です。
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]再帰が明らかに適している場合
再帰は、問題に木のような構造があり、それを呼び出しグラフに直接対応させられる場合、ベースケースが自然に定義できる場合、そして深さが制限されている場合（平衡木や分割統治では O(log n)）に力を発揮します。例として、JSON の解析、ディレクトリの走査、ゲーム木、バックトラッキング問題などがあります。このような場合、再帰によるコードは同等の反復版より短く、明快で、正しさも証明しやすくなります。
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]反復が明らかに適している場合
次のような場合は反復を選ぶべきです。深さが O(n) で n が大きい場合（安全な Python コードではおよそ 500 を超える場合）、再帰版と反復版の読みやすさが同程度の場合（フィボナッチ数列、階乗）、または問題が本質的に逐次的で、自然な部分問題への分解がない場合です。配列を左から右へ処理する単純なループ（累積和、スライディングウィンドウ、二つのポインタ）は、常に反復で実装してください。
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceDFSの再帰を反復に変換する
体系的な方法は、再帰的な DFS の引数を明示的なスタックに積むことで、どの再帰的 DFS も反復に変換することです。重要な点は、再帰呼び出し f(args) が、args を積んでループする処理と等価だということです。後順処理（親を処理する前に子の結果が必要な場合）では、2 パス方式または訪問済みフラグが必要になることがあります。
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]再帰のパフォーマンス上のオーバーヘッド
Python では、再帰呼び出しごとに無視できないオーバーヘッドが発生します。新しいフレームが作成され（ヒープ上にメモリが割り当てられ）、ローカル変数が初期化され、戻り先のアドレスを保持するポインタが保存されます。ベンチマークによると、Python の関数呼び出しのオーバーヘッドは、1 回あたりおよそ 100～200 ナノ秒です。再帰の深さが 10^6 の場合、アルゴリズム本体の処理とは無関係に、純粋なオーバーヘッドだけで 0.1～0.2 秒になります。反復ループでは、このオーバーヘッドを完全に回避できます。
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')面接での判断
コーディング面接で選択肢がある場合は、次のように考えてください。「再帰の深さは O(log n) に制限されていますか？」答えが yes なら、再帰で問題ありません。「再帰の深さは O(n) ですか？」その場合は反復を優先するか、本番環境では反復に変換すると説明してください。「問題は自然に木構造または分割統治の形になっていますか？」その場合は再帰を選ぶ方向で考えます。「問題は逐次的な走査ですか？」その場合は反復を使います。
必ず理由も説明してください。たとえば、「ここでは再帰を使います。平衡 BST では深さが O(log n) なので、スタック空間 O(log n) は許容できるためです」と述べます。
まとめ：トレードオフ表
トレードオフをまとめると、再帰コードは短く、問題の構造を反映することが多い一方、深さに比例する O(depth) のスタック空間を消費し、関数呼び出しのオーバーヘッドも発生します。反復コードは長くなりますが、スタック空間は O(1) で、再帰の深さ制限も回避できます。メモ化再帰（次のレッスンで扱います）は中間的な選択肢です。再帰の明快さを保ちながら、重複した再計算をなくせます。解法を分析するときは、コールスタックの空間も含めて、空間計算量を必ず明示してください。
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、深さが O(log n) の場合や問題が自然な木構造になっている場合は再帰を、深さが O(n) の場合や問題が逐次的な場合は反復を選ぶこと、素朴な再帰版フィボナッチ数列は O(2^n) であり、反復版は時間計算量 O(n)、空間計算量 O(1) であること、そして再帰的な DFS は、ヒープ上の明示的なスタックを管理することで反復に変換できることを学びました。次は、メモ化を使って重複した再帰呼び出しをなくします。
よくある質問
「再帰と反復のトレードオフ」レッスンは無料ですか？
はい。「再帰と反復のトレードオフ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「再帰と反復のトレードオフ」で何を学びますか？
再帰的な階乗とFibonacciを反復ループに変換し、Pythonの再帰上限やスタックサイズによって反復が適する場合を説明します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「再帰と反復のトレードオフ」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 再帰の枠組み：基底ケース、信頼、構築
- コールスタックを可視化する
- 再帰と反復のトレードオフ
- メモ化：再帰結果をキャッシュする