递归程序空间复杂度的差异

Question

我想知道空间复杂度最低的递归程序和非递归程序的空间复杂度之间的区别，我知道递归在其操作中使用堆栈，但递归总是增加空间complexity.Can递归有助于降低空间复杂度吗?我也将感谢对recursion.Please中堆栈使用的良好教程的任何指导，如果可能的话，也提供了一个简短的说明示例。

Answer 1

递归可以增加空间复杂度，但不会减少。例如，考虑插入到二进制搜索树。非递归实现(使用时间循环)使用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);