algorithm - 使用递归程序的空间复杂度差异

Question

我想知道空间复杂度最低的递归程序和非递归程序的空间复杂度之间的差异（更大或更小）。我知道递归在其操作中使用堆栈，但递归总是会增加空间复杂度。递归是否有助于减少空间复杂性？我也将感谢任何关于递归中堆栈使用的良好教程的指导。如果可能，还请提供一个简短的示例以进行说明。

Answer 1

递归可以增加空间复杂度，但永远不会降低。例如考虑插入二叉搜索树。非递归实现（使用 while 循环）使用 O(1) 内存。递归实现使用 O(h) 内存（其中 h 是树的深度）。

更正式地说：如果有一个空间复杂度为 O(X) 的递归算法，那么总会有一个空间复杂度为 O(X) 的非递归算法（你可以通过使用堆栈来模拟递归）。但事实并非如此（参见上面的示例）。

Answer 2

如果您的实现语言支持TCO，您可以使用尾递归实现与循环迭代完全相同的空间复杂度。

int acc=1;
(for int i=1; i<=n; i++) {
  acc*=i;
}
return acc;

是相同的：

int fact (int i, int acc) {
  if( i == 1) 
     return acc;
  return fact(i--, i*acc);
}
return fact(n);