是否存在只有递归解决方案的问题？

Question

可能重复:
是否存在仅具有递归解决方案的问题？
每次递归都可以转换成迭代吗？
命令式语言中"递归"的"必要"用法

是否有一个只有一个递归解决方案,那就是,有一个递归解决问题的问题,而是一个迭代的解决方案还没有被发现,或者更好的是,已被证明是不存在的(显然,这不是一个尾递归)？

Answer 1

通过将参数推送到堆栈来替换函数调用,并从弹出堆栈返回,并且您已经消除了递归.

编辑:响应"使用堆栈不会降低空间成本"

如果递归算法可以在恒定空间中运行,则可以以尾递归方式编写.如果它是以尾递归格式编写的,那么任何体面的编译器都可以崩溃堆栈.但是,这意味着"转换函数调用显式堆栈推送"方法也会占用恒定空间.举个例子,让我们考虑因子.

阶乘:

def fact_rec(n):
    ' Textbook Factorial function '
    if n < 2:  return 1
    else:      return n * f(n-1)


def f(n, product=1):
    ' Tail-recursive factorial function '
    if n < 2: return product
    else:     return f(n-1, product*n)

def f(n):
    ' explicit stack -- otherwise same as tail-recursive function '
    stack, product = [n], 1
    while len(stack):
        n = stack.pop()
        if n < 2: pass 
        else:
            stack.append(n-1)
            product *= n
    return product

因为stack.pop()跟在循环中的stack.append()之后,堆栈中永远不会有多个项目,因此它满足了常量空间要求.如果您想象使用临时变量而不是1长度堆栈,它将成为您的标准迭代因子算法.

当然,有递归函数不能以尾递归格式编写.您仍然可以使用某种堆栈转换为迭代格式,但如果对空间复杂性有任何保证,我会感到惊讶.

Answer 2

在响应Ackermann函数答案时,这是一个非常直接的转换 - 调用堆栈 - 实际堆栈问题.这也显示了迭代版本的一个好处.

在我的平台上(Python 3.1rc2/Vista32),迭代版本计算ack(3,7)= 1021罚款,而递归版本stackoverflows.注意:它在不同的机器上没有在python 2.6.2/Vista64上进行stackoverflow,因此它似乎与平台相关,

(社区维基,因为这实际上是对另一个答案的评论[如果只有评论支持代码格式化....])

def ack(m,n):
  s = [m]
  while len(s):
     m = s.pop()
     if m == 0:
        n += 1 
     elif n == 0:
        s.append(m-1)
        n = 1
     else:
        s.append(m-1)
        s.append(m)
        n -= 1
  return n

Answer 3

该阿克曼函数不能没有递归表达

Answer 4

你可以定义一个没有递归的图灵机(对吧？)因此语言不需要递归才能完成图灵.

Answer 5

在编程中,递归实际上是迭代的一种特殊情况 - 您可以使用调用堆栈作为存储状态的特殊方法.您可以将任何递归方法重写为迭代方法.它可能更复杂或更不优雅,但它是等价的.

在数学中,有一些问题需要递归技术来得出答案 - 一些例子是找到根(牛顿方法),计算素数,图优化等.但是,即使在这里,也只是一个问题,你如何区分术语"迭代"和"递归".

编辑:正如其他人所指出的,存在许多函数,其定义是递归的 - 例如.在阿克曼功能.但是,这并不意味着它们无法使用迭代结构进行计算 - 只要您拥有图灵完整操作集和无限内存.