如何测量调用堆栈的长度？

Question

最近有一道测试题询问 fact1 的调用堆栈“有多深”，其中 n = 5。这是代码：

int fact1(int n)
{
    if (n == 1)
    {
        return 1
    }
    else {
        return n * fact(n-1)
    }
}

测试的答案是5个，但我认为是4个。我不相信第一次调用是计算调用次数。

Answer 1

实际上，每个函数调用都在调用堆栈中结束。

你的例子看起来像C；在 C 中，总有一个 main 函数；即使 main 函数在调用堆栈上结束。

我不认为有一种方法可以检查 C 中的调用堆栈；特别是因为允许编译器优化它想要的任何东西。例如，它可以优化 tail-recursion，然后调用堆栈会比您预期的要小。

在Python中，调用堆栈很容易检查；通过抛出异常（例如 assert(False)），只要你想，就可以让函数崩溃。然后程序将产生一条错误消息，其中包含完整的“堆栈跟踪”，包括堆栈中每个函数的列表。

这是 python 中的堆栈跟踪示例：

def fact1(n):
    assert(n != 1)
    return n * fact1(n-1)

def main():
    f = fact1(3)
    print(f)

main()

输出：

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in main
  File "<stdin>", line 3, in fact1
  File "<stdin>", line 3, in fact1
  File "<stdin>", line 2, in fact1
AssertionError

另一个例子只是为了好玩：

def print_even(n):
    if (n <= 1):
        print('yes' if n == 0 else 'no')
        assert(False)
    else:
        print_odd(n-1)

def print_odd(n):
    if (n <= 1):
        print('yes' if n == 1 else 'no')
        assert(False)
    else:
        print_even(n-1)

def main():
    n = 5
    print('Is {} even?'.format(n))
    print_even(n)

main()

输出：

Is 5 even?
no
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in main
  File "<stdin>", line 6, in print_even
  File "<stdin>", line 6, in print_odd
  File "<stdin>", line 6, in print_even
  File "<stdin>", line 6, in print_odd
  File "<stdin>", line 4, in print_even
AssertionError

如何测量调用堆栈的长度？

How to measure the length of a call stack?

recursion