递归函数的空间复杂度

Question

给定以下函数：

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n - 1) + f(n - 1);
} 

我知道大O时间复杂度为O(2^N)，因为每次调用函数都会调用两次。

我不理解的是为什么空间/内存复杂度为O(N)？

- George Kagan

---

您的意思是返回类似于斐波那契数列的 f(n-1) + f(n-2) 吗？ - Nic Scozzaro

相关链接：https://dev59.com/6FwX5IYBdhLWcg3wnwnd - jdhao

Answer 1

一种解决这类问题的有用方法是考虑递归树。要识别递归函数的两个特征：

1. 树的深度（在基本情况下执行多少个返回语句）
2. 树的宽度（进行多少次递归函数调用）

我们的递归关系式为T(n) = 2T(n-1)。正如您正确指出的那样，时间复杂度为O(2^n)，但让我们看看它与我们的递归树的关系。

      C
     / \         
    /   \      
T(n-1)  T(n-1)

            C
       ____/ \____
      /           \
    C              C   
   /  \           /  \
  /    \         /    \
T(n-2) T(n-2) T(n-2)  T(n-2)

这个模式会一直持续，直到我们的基本情况出现，它将看起来像下面的图片：

随着每个树层，我们的n减少1。因此，在到达基本情况之前，我们的树将具有n的深度。由于每个节点有2个分支，我们总共有n个层级，所以我们的总节点数是2^n，使得我们的时间复杂度为O(2^n)。我们的内存复杂度取决于返回语句的数量，因为每个函数调用都将存储在程序堆栈上。一般而言，递归函数的内存复杂度为O（递归深度）。由于我们的树深度表明，我们将拥有n个总的返回语句，因此内存复杂度为O(n)。

- Ritwik Biswas

---

这个问题更加清晰明了。请问您需要翻译成简体中文还是繁体中文呢？ - arielorvits

引用此答案的关键观点：“内存复杂度取决于返回语句的数量，因为每个函数调用都将存储在程序堆栈中。一般而言，递归函数的内存复杂度为O（递归深度）。由于我们的树深度表明，我们将有n个总的返回语句，因此内存复杂度为O（n）。”但这是否意味着所有递归调用都具有O（n）空间复杂度？（函数始终只返回一次，对吗？） - Akshay Lokur

Answer 2

以下是我的思考：

• 人们往往认为，空间复杂度也应该是O(2^N)，因为毕竟每次递归调用都需要为O(2^N)个数据分配内存，对吗？（答案是否定的）
• 实际上，在每次调用中，这些值会相互叠加/折叠，因此所需的空间只是每次从基本情况开始形成数组 [f(1), f(2), f(3)...f(n)] 的结果，换句话说，只需要 O(n) 的内存。

- Nic Scozzaro

Answer 3

我在两篇文章中找到了一个清晰的答案。

第一篇

在这篇文章中，它告诉我为什么空间复杂度是O(n)。

但我也很困惑，为什么堆栈帧只有f(5) -> f(4) -> f(3) -> f(2) -> f(1)而没有f(5) -> f(4) -> f(3) -> f(2) -> f(0)和其他的同时存在。

斐波那契树图像：

然后我在第二篇文章里找到了答案，解决了我的困惑。

第二篇文章

这个 文章 很有帮助，你可以在这里看到详情。

堆栈帧 图像：

谢谢。

- luoochen

Answer 4

这可以通过考虑不同的函数更好地解释
f(n) = f(n-1) + f(n-2)
f(0) =0, f(1)=1

这将导致以下计算f(4)的树形结构

      f(4)
   f(3)      f(2)
 f(2)   f(1)  f(1)  f(0)
f(1) f(0)

系统可以使用重复存储堆栈来处理深度相等的所有节点（f(0), f(1), f(2), f(3)和f(4)的存储单元）。而运行时需要考虑每个节点上的所有操作（加法或返回语句）- 因此是节点中任何一个因素的因素。

- Redsha

Answer 5

递归问题可以看作是使用栈来实现，所以如果第一个函数调用自身，第二个函数就会暂停并依次遍历到末尾并一次添加到栈中，在完成后返回，并一次从最顶部的栈中删除。然后第二个函数恢复并遍历到末尾并添加到最顶部的栈中，在返回时移除。但它使用相同的堆栈，在相同的堆栈下最多需要n个空间，因此空间复杂度为O(n)。

- prashant sargar

---

请花些时间清理您的帖子语法。长句极其难以理解。 - General Grievance

Answer 6

每次调用都会向堆栈中添加一个级别。

f(4)

f(3) f(2) f(1) f(0)

这些调用都被添加到调用栈中并占用实际内存。 然而，仅仅因为你有n个调用总数并不意味着它需要O(n)的空间。 因此，这将需要O(n)的空间。

- Rishabh Singh