哪些递归函数不能使用循环重写？

Question

据我所知,大多数递归函数可以使用循环重写.有些可能比其他人更难,但大多数都可以重写.

在哪些情况下,使用循环重写递归函数是不可能的(如果存在这样的条件)？

Answer 1

当您以递归方式使用函数时,编译器会为您处理堆栈管理,这使得递归成为可能.你可以递归地执行任何操作,你可以通过自己管理堆栈来做(对于间接递归,你只需要确保你的不同函数共享该堆栈).

所以,不,没有什么可以通过递归来完成,并且不能通过循环和堆栈来完成.

@Abhinav:很抱歉回复一个非常老的帖子,但这引起了我的注意,并且有一个简单的证据表明答案是肯定的:图灵机通过执行一个循环完成它所做的一切:1.获取指令,2.评估它,3.转到1. (3认同)
@VickyChijwani:mokus的证明对于他提到的范围是完全完整的,并且不那么容易混淆,他可以说,"所有程序和子程序都在一个简单的单循环中执行......",所以,递归是一个小心的抽象类似于任何更高级别的编程控制构造的堆栈管理是对处理器管道最终将做什么的抽象,获取指令并执行它们.因此,在某些级别的删除抽象中,所有程序都是单循环. (3认同)

Answer 2

可以使任何递归函数迭代(进入循环),但您需要自己使用堆栈来保持状态.

通常,尾递归很容易转换为循环:

A(x) {
  if x<0 return 0;
  return something(x) + A(x-1)
}

可以翻译成:

A(x) {
  temp = 0;
  for i in 0..x {
    temp = temp + something(i);
  }
  return temp;
}

可以转换为尾递归的其他类型的递归也很容易改变.另一个需要更多的工作.

下列:

treeSum(tree) {
  if tree=nil then 0
  else tree.value + treeSum(tree.left) + treeSum(tree.right);
}

翻译不是那么容易.您可以删除一个递归,但如果没有一个结构来保持状态,则另一个递归是不可能的.

treeSum(tree) {
  walk = tree;
  temp = 0;
  while walk != nil {
    temp = temp + walk.value + treeSum(walk.right);
    walk = walk.left;
  }
}

Answer 3

每个递归函数都可以用一个循环实现.

只要想想处理器的作用,它就会在一个循环中执行指令.

Answer 4

我不知道递归函数无法转换为迭代版本的示例,但不切实际或效率极低的示例如下:

基本上,任何你必须开始跟踪无限潜在状态的东西.

Answer 5

问题不在于它们不能用循环来实现,而是递归算法的工作方式,它更清晰,更简洁(在许多情况下在数学上可证明)函数是正确的.

许多递归函数可以写成尾循环递归,可以优化为循环,但这取决于算法和使用的语言.