コールスタックを可視化する

呼び出しスタックとは

import traceback

def outer():
    inner()

def inner():
    # Print the current call stack
    traceback.print_stack()

outer()
# Shows: module -> outer -> inner

sysでスタックフレームを観察する

import sys

def countdown(n):
    depth = 0
    frame = sys._getframe(0)
    while frame:
        depth += 1
        frame = frame.f_back
    print(' ' * (n * 2) + f'countdown({n}) called, stack depth={depth}')
    if n <= 0:
        return
    countdown(n - 1)
    print(' ' * (n * 2) + f'countdown({n}) returning')

countdown(3)

呼び出しスタック上で階乗を追跡する

def factorial(n, indent=0):
    prefix = '  ' * indent
    print(prefix + f'-> factorial({n})')
    if n == 0:
        print(prefix + '<- returns 1')
        return 1
    result = n * factorial(n - 1, indent + 1)
    print(prefix + f'<- returns {result}')
    return result

factorial(4)

スタックオーバーフロー：Pythonの再帰制限

import sys

print('Recursion limit:', sys.getrecursionlimit())

def deep_recursion(n):
    if n == 0:
        return 0
    return 1 + deep_recursion(n - 1)

# Safe: within limit
try:
    print(deep_recursion(900))
except RecursionError:
    print('Overflow at 900')

# Overflow
try:
    print(deep_recursion(2000))
except RecursionError:
    print('RecursionError at 2000 — limit exceeded!')

再帰制限を引き上げる

import sys

# Only increase when you are certain of the maximum depth
# and have confirmed it is safe
original = sys.getrecursionlimit()
sys.setrecursionlimit(5000)

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(3000))  # Works with increased limit
sys.setrecursionlimit(original)  # restore
print('Limit restored:', sys.getrecursionlimit())

相互再帰における呼び出しスタック

def is_even(n):
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n):
    if n == 0:
        return False
    return is_even(n - 1)

# Stack alternates: is_even(4)->is_odd(3)->is_even(2)->is_odd(1)->is_even(0)
print(is_even(4))  # True
print(is_odd(5))   # True
print(is_even(7))  # False

末尾呼び出しとPythonが最適化しない理由

# Tail-recursive factorial (accumulator pattern)
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)  # tail call

# In Python, this still uses O(n) stack space (no TCO)
# But it IS semantically tail-recursive
print(factorial_tail(6))   # 720
print(factorial_tail(10))  # 3628800

# Iterative version: same logic, O(1) stack
def factorial_iter(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

print(factorial_iter(10))  # 3628800

再帰木を出力する

def fib_traced(n, indent=0):
    prefix = '  ' * indent
    print(prefix + f'fib({n})')
    if n <= 1:
        print(prefix + f'=> {n}')
        return n
    result = fib_traced(n-1, indent+1) + fib_traced(n-2, indent+1)
    print(prefix + f'=> {result}')
    return result

fib_traced(4)
# Shows the branching tree with duplicated sub-problems

スタックの深さと空間計算量

# Recursion depth = space complexity

# Linear recursion: O(n) stack
def linear_depth(n):
    if n == 0: return 0
    return 1 + linear_depth(n - 1)  # depth = n

# Logarithmic recursion: O(log n) stack
def log_depth(n):
    if n <= 1: return 0
    return 1 + log_depth(n // 2)    # depth = log2(n)

print('n=32 linear depth:', 32)
print('n=32 log depth:', log_depth(32))     # 5
print('n=1024 log depth:', log_depth(1024)) # 10

明示的なスタックで再帰を反復に変換する

# Recursive inorder traversal -> iterative with explicit stack
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val   = val
        self.left  = left
        self.right = right

def inorder_iterative(root):
    result = []
    stack  = []
    curr   = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(inorder_iterative(root))  # [1, 2, 3, 4, 6]

まとめ：呼び出しスタックと空間計算量

理解度チェック

レッスンのまとめ