递归限制是包含的还是不包含的，额外的堆栈帧来自哪里? [英] Is the recursion limit inclusive or exclusive and where do extra stack frames come from?

问题描述

我有这个递归阶乘函数:

def factorial(n):如果 n <2:返回 1返回 n * 阶乘(n-1)

执行factorial(998) 有效，但factorial(999) 会引发RecursionError:比较时超出最大递归深度.>

为什么它在 factorial(999) 而不是 1000 或 1001 处出错?factorial(1) 命中基本情况，因此调用 factorial 函数应该只有一个堆栈帧，factorial(2) 递归一次，所以它应该使用 2 个堆栈帧等等.

递归限制是互斥的还是包含的?例如，如果您 setrecursionlimit(1000) 在 达到 1000 个堆栈帧或超过 1000 个堆栈帧时会出错?

如果是独占的，为什么会在 n=999 而不是 n=1000 上出错?n=999 应该创建 999 个帧，而不是 1000 个.额外的堆栈帧来自哪里使它达到 1000?如果限制是包含在内的，那么额外的 2 个堆栈帧来自哪里，使其达到 1001 个堆栈帧?

解决方案

请自行查看.Python 有很棒的内省工具:

导入检查定义阶乘(n):如果 n <2:返回 1打印(len(inspect.stack()))返回 n * 阶乘(n-1)

全局级别已经是 1 级深度.第一个函数调用是 2 深度的，因此在您的计算中有一个额外"的堆栈框架.

def f():打印(len(inspect.stack()))打印(len(inspect.stack())) # 1f() # 2

I have this recursive factorial function:

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n-1)

Doing factorial(998) works, but factorial(999) will raise a RecursionError: maximum recursion depth exceeded in comparison.

Why does it error at factorial(999) and not 1000 or 1001? factorial(1) hits the base case, so there should only be one stack frame from calling the factorial function, factorial(2) recurses once, so it should use 2 stack frames and so on.

Is the recursion limit exclusive or inclusive? As in, if you setrecursionlimit(1000) does it error when you reach 1000 stack frames or when you exceed 1000?

If it's exlusive, why does it error on n=999 instead of n=1000? n=999 should create 999 frames, not 1000. Where does the extra stack frame come from that makes it hit 1000? If the limit is inclusive, where do the extra 2 stack frames come from that make it hit 1001 stack frames?

解决方案

See for yourself. Python has great introspection tools:

import inspect

def factorial(n):
    if n < 2:
        return 1
    print(len(inspect.stack()))
    return n * factorial(n-1)

Global level is already at 1-depth. First function call is 2-depth, so there's a one 'extra' stack frame in your calculations.

def f():
    print(len(inspect.stack()))

print(len(inspect.stack())) # 1
f() # 2

这篇关于递归限制是包含的还是不包含的，额外的堆栈帧来自哪里?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！