调用树的调用栈
Call stack for call trees
我对递归函数如何使用内存创建“调用堆栈”有一个大概的了解，但我对这个概念有疑问。让我们假设我们有一个函数，例如 factorial()，它在每个递归步骤中调用自己一次。另一方面，有作为斐波那契数字生成器的函数，它在每一步中调用自己两次。假设两个函数的递归调用总数相同，斐波那契函数会比阶乘函数使用更多内存吗？
一开始，对于栈中的一个阶乘（如下图），先是5，然后是4，然后是3比1，每一个占一个堆栈中每次调用阶乘函数的内存，这取决于 递归树 的高度。它应该是 5 个内存单元，最后，如果它的输入是 n，space 复杂度是 n 的顺序。返回值1后，函数returns和变量在栈中一一消失。事实上，上升趋势（纠正每个函数调用中的变量）和下降趋势（当我们完成每个函数的工作时）。
但是对于Fibonacci，首先，值为5，Fibonacci函数被调用，值为4和3，首先转到Fib 3（左分支）。因为先要算出来，然后去Fib4.In栈（我没画出来）我们有两个值。然后4的fib变成3的fib加上2的fib。首先计算3的fib，然后是2的fib。到目前为止我们已经在内存中存储了3个变量（5,4,3）。同样，我做的编号消耗多达 5 个内存单元（5、4、3、2、1，它是树的最高高度）。所以对于n作为输入，space复杂度是n的阶数。所以他们是平等的。
图片：
enter image description here
我对递归函数如何使用内存创建“调用堆栈”有一个大概的了解，但我对这个概念有疑问。让我们假设我们有一个函数，例如 factorial()，它在每个递归步骤中调用自己一次。另一方面，有作为斐波那契数字生成器的函数，它在每一步中调用自己两次。假设两个函数的递归调用总数相同，斐波那契函数会比阶乘函数使用更多内存吗？
一开始，对于栈中的一个阶乘（如下图），先是5，然后是4，然后是3比1，每一个占一个堆栈中每次调用阶乘函数的内存，这取决于 递归树 的高度。它应该是 5 个内存单元，最后，如果它的输入是 n，space 复杂度是 n 的顺序。返回值1后，函数returns和变量在栈中一一消失。事实上，上升趋势（纠正每个函数调用中的变量）和下降趋势（当我们完成每个函数的工作时）。
但是对于Fibonacci，首先，值为5，Fibonacci函数被调用，值为4和3，首先转到Fib 3（左分支）。因为先要算出来，然后去Fib4.In栈（我没画出来）我们有两个值。然后4的fib变成3的fib加上2的fib。首先计算3的fib，然后是2的fib。到目前为止我们已经在内存中存储了3个变量（5,4,3）。同样，我做的编号消耗多达 5 个内存单元（5、4、3、2、1，它是树的最高高度）。所以对于n作为输入，space复杂度是n的阶数。所以他们是平等的。
图片： enter image description here