RecursionError: maximum recursion depth exceeded

1
2
3
4
5

# NG: 終了条件がない
def infinite():
    return infinite()

infinite()  # RecursionError

1
2
3
4
5
6

# NG: 終了条件に到達しない
def countdown(n):
    print(n)
    countdown(n - 1)  # n == 0 でも止まらない

countdown(5)

1
2
3
4
5
6
7

# NG: 大きな入力で深くなりすぎる
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(10000)  # RecursionError

1
2
3
4
5

def countdown(n):
    if n <= 0:  # 終了条件
        return
    print(n)
    countdown(n - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# 再帰版
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

# ループ版（推奨）
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

1
2
3
4
5
6
7

import sys

# 現在の上限を確認
print(sys.getrecursionlimit())  # 1000

# 上限を変更（注意: スタックオーバーフローの危険）
sys.setrecursionlimit(3000)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# Pythonは末尾再帰最適化をサポートしていない
# 手動でループに変換する

def tail_recursive_factorial(n, acc=1):
    if n <= 1:
        return acc
    return tail_recursive_factorial(n - 1, n * acc)

# ループ版に変換
def factorial(n):
    acc = 1
    while n > 1:
        acc *= n
        n -= 1
    return acc

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n < 2:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

# 深さを減らしながら計算
for i in range(0, 10000, 100):
    fibonacci(i)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def tree_traversal_recursive(node):
    if node is None:
        return
    print(node.value)
    tree_traversal_recursive(node.left)
    tree_traversal_recursive(node.right)

# スタックを使った実装
def tree_traversal_iterative(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.value)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)