如何计算在 Python 中计算 n 的阶乘的递归调用次数

Question

我想写一个名为recursive_factorial(n)的递归函数，它以一个非负整数作为参数并计算factorial(n)的结果。函数 returns 一个元组包含结果和按顺序进行的递归调用的次数。

-- 第一个函数调用不算为递归调用。

def recursive_factorial(n):
    if n == 0:
        return 1, 0
    else:
        value,step = recursive_factorial(n-1)
        return n * value, step + 1

测试和输出：

>> print(recursive_factorial(1))
(1, 0) --- Expected
(1, 1) --- Gotten

>> print(recursive_factorial(3))
(6, 2) --- Expected
(6, 3) --- Gotten

>> print(recursive_factorial(8))
(40320, 7) --- Expected
(40320, 8) --- Gotten

Answer 1

如果你想计算递归调用的次数，你的期望是错误的，因为你没有计算 n=1 的调用。

为了通过示例向您展示这一点，让我们假设您调用 recursive_factorial(3)。调用堆栈将是

recursive_factorial(3)
recursive_factorial(2)
recursive_factorial(1)
recursive_factorial(0)

既然你说你没有计算 n=0 的情况，预期计数应该是 3，而不是你预期的 2

如果您希望计数器符合当前预期，您必须添加另一个基本案例

def recursive_factorial(n):
if n == 0 or n ==1:
    return 1, 0
else:
    value,step = recursive_factorial(n-1)
    return n * value, step + 1

如何计算在 Python 中计算 n 的阶乘的递归调用次数

How to count the number of recursive calls made to calculate the factorial of n in Python

python

recursion