再帰と再帰木法
再帰呼び出しを木構造として追跡し、Master Theoremを適用して、マージソート、階乗、Fibonacciの派生問題の時間計算量を導きます。
「再帰と再帰木法」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
再帰とコールスタック
関数が自分自身を呼び出すと、呼び出しごとにスタックフレームが追加されます。ベースケースに到達するまで積み上がり、その後、順番に戻っていきます。これをイメージすることが、再帰を分析する第一歩です。
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive call
# Call chain: factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# 1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5)) # 120フィボナッチ数列の再帰木
再帰木では、各呼び出しをその内部の呼び出しへ展開します。素朴なフィボナッチ数列の実装では毎回2つに分岐するため、約2^n個のノードを持つ木になり、計算量はO(2^n)です。コードを確認してください。
call_count = [0]
def fib_naive(n):
call_count[0] += 1
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
for n in [5, 10, 15, 20]:
call_count[0] = 0
result = fib_naive(n)
print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1繰り返される部分問題を見つける
この木では、fib(3)のような同じ呼び出しが複数の分岐にわたって繰り返されます。この重複部分問題はメモ化のサインです。メモ化によって、O(2^n)をO(n)まで削減できます。
# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
call_count2 = [0]
def fib_counted(n, memo={}):
call_count2[0] += 1
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
return memo[n]
fib_counted(20)
print(f'calls with memo: {call_count2[0]}') # only 21マージソートの再帰木
マージソートの木にはlog n個のレベルがあり、各レベルでは合計O(n)の処理を行います。すべての要素を1回ずつ処理するためです。これらを掛け合わせるとO(n log n)になります。コードを確認してください。
# Merge sort: at each level, n total elements are merged
# Level 0: 1 merge of n elements -> n work
# Level 1: 2 merges of n/2 each -> n work
# Level 2: 4 merges of n/4 each -> n work
# ...log(n) levels...
# Total: n * log(n)
# Verify with operation counter:
def merge_sort_counted(arr):
ops = [0]
def _sort(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r = _sort(a[:m]), _sort(a[m:])
result, i, j = [], 0, 0
while i < len(l) and j < len(r):
ops[0] += 1
if l[i] <= r[j]: result.append(l[i]); i+=1
else: result.append(r[j]); j+=1
return result + l[i:] + r[j:]
return _sort(arr), ops[0]
_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}') # ~384 ~ 64*log2(64)=384マスター定理
マスター定理は、T(n) = a*T(n/b) + O(n^d)という漸化式を3つのケースで解きます。マージソートでは（a=2、b=2、d=1）、O(n log n)が得られます。試験に備えて、3つのケースを覚えておきましょう。
# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d => O(n log n)
# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d => O(log n)
# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)
import math
print('log2(7) =', math.log2(7)) # 2.807...再帰木を描く: ステップごとの手順
再帰木を描くには、最上部にT(n)を置き、各呼び出しを展開し、各レベルの処理量を合計してから、レベル数を掛けます。自然にできるようになるまで練習してください。
# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)
# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)
# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)
def count_recursive_calls(n, results=[]):
if n <= 1:
results.append(n)
return n
return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)
results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')指数時間の再帰: 部分集合
すべての部分集合を生成する処理はO(2^n)です。部分集合は正確に2^n個あるため、これより速くすることはできません。各要素を含めるか含めないかによって選択肢が分岐し、二分木が構築されます。コードを確認してください。
def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current)) # O(n) copy
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss)) # 8 = 2^3
print(ss)末尾再帰と最適化
末尾再帰とは、再帰呼び出しが処理の最後のステップになっている形です。言語によっては、その呼び出しに同じフレームを再利用できますが、Pythonは対応していません。そのため、深い再帰ではスタックがあふれます。代わりにループを使用してください。
# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
if n == 0:
return acc
return fact_tail(n - 1, n * acc) # tail call
# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(fact_tail(10)) # 3628800
print(fact_iter(10)) # 3628800再帰の空間計算量
再帰呼び出しごとにフレームを保持するため、再帰の空間計算量はO(深さ)です。線形再帰はO(n)、平衡木のDFSはO(log n)です。深くなりすぎるとRecursionErrorが発生します。
import sys
print(sys.getrecursionlimit()) # default 1000
# Increase limit for deep problems
sys.setrecursionlimit(10000)
# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
max_seen[0] = max(max_seen[0], depth)
if n <= 0:
return
max_depth_tracker(n - 1, depth + 1, max_seen)
return max_seen[0]
print(max_depth_tracker(50)) # 50 => O(n) stack framesクイックソートの再帰木
クイックソートは、適切なピボットを選べばO(n log n)ですが、ソート済みの入力で悪いピボットを選ぶとO(n^2)まで悪化します。そのため、ピボットをランダム化することが重要です。コードを確認してください。
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # randomised -> O(n log n) expected
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # sortedべき乗関数: O(log n)の再帰
素朴なx^nの計算ではO(n)回の乗算が必要ですが、二乗法を使うと各ステップで処理量を半分にできます。x^n = (x^(n/2))^2のように計算するためです。これにより、半分に縮小する処理を活用した明快なO(log n)になります。コードを確認してください。
def fast_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / fast_pow(x, -n)
if n % 2 == 0:
half = fast_pow(x, n // 2)
return half * half # O(log n) calls
return x * fast_pow(x, n - 1)
print(fast_pow(2, 10)) # 1024
print(fast_pow(3, 5)) # 243
# Only log2(10)=3-4 recursive calls for n=10クイックチェック
クイックチェックです。再帰木の手法から何を学んだか確認しましょう。1問だけです。時間をかけて取り組んでください。🌳
レッスンの振り返り
振り返り: 再帰木によって処理全体の量が分かり、マスター定理によって分割統治の漸化式を解けます。また、再帰にはO(深さ)のスタック領域が必要です。
よくある質問
「再帰と再帰木法」レッスンは無料ですか？
はい。「再帰と再帰木法」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「再帰と再帰木法」で何を学びますか？
再帰呼び出しを木構造として追跡し、Master Theoremを適用して、マージソート、階乗、Fibonacciの派生問題の時間計算量を導きます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「再帰と再帰木法」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。