logo标签列表

只有递归解决方案的问题存在吗？（这是一个关于IT技术的问题标题）

algorithmrecursion
17
3
这取决于你所谓的递归是什么意思。每个递归函数都可以通过实现堆栈来转换为非递归函数。 - yairchu
76
是的；这里有详细描述：https://dev59.com/0nNA5IYBdhLWcg3wF5uO - Marc Gravell
1
@Marc Gravell：太棒了，当我们查看K＆R中递归的索引时，我们可以找到相同的内容。（索引引用了一堆页面和索引页...） - LB40
1
我认为这更多是“在迭代与递归相比非常糟糕的情况下存在任何问题”而不是“是否存在绝对需要递归的问题”。 - GManNickG
我认为这里的问题不在于递归算法是否总能被转化为迭代算法（答案是肯定的[1]），而在于是否存在一类只能用递归表达的问题。对于这个问题，答案也是肯定的。例如，确定某个数字序列是否出现在圆周率的无限扩展中[2]。[1] https://dev59.com/FHNA5IYBdhLWcg3wgeOk [2] https://mathoverflow.net/questions/23547/does-pi-contain-1000-consecutive-zeroes-in-base-10 - Hardest
显示剩余3条评论
8个回答
19

用将函数调用替换为将参数推入堆栈，用返回弹出堆栈的方式来代替递归调用，就可以消除递归。

编辑：回应“使用堆栈不会减少空间成本”

如果一个递归算法可以在常量空间内运行，那么它可以以尾递归的方式编写。如果它以尾递归格式编写，那么任何合理的编译器都可以折叠堆栈。然而，这意味着“将函数调用转换为显式堆栈推送”方法也需要常量空间。以阶乘为例。

阶乘：

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长度堆栈，它将成为您的标准迭代阶乘算法。

当然，存在无法以尾递归格式编写的递归函数。您仍然可以使用某种类型的堆栈转换为迭代格式，但如果没有关于空间复杂度的保证，我会感到惊讶。

2
这并不是递归消除。当将递归函数替换为非递归函数时，应该使用有限的内存，而不是理论上无限的堆栈。 - Kirill V. Lyadvinsky
3
“保证使用有限的内存”并不是非递归函数的定义。这可能是一个理想的特性，但它不是一个定义性的要求。一个具有内存泄漏的迭代算法将会使用潜在无限量的内存，但是没有人会认为仅此就使得算法是递归的。 - Chuck
2
@jia3ep：这是递归消除。实际上，在某些情况下，通过将负载从操作系统的调用堆栈（在许多架构中具有有限空间）移动到堆中，避免了函数调用的开销，因此已经带来了有形的好处。 - Jimmy
在我看来，这并不改变递归的概念，你同样可以以一些非栈的方式嵌入虚拟机，并在其上运行递归代码，我更多地考虑了一种不同算法的精神。尽管如此，这是个好主意。 - Liran Orevi
@Jimmy，硬件堆栈比使用堆要快得多，因此堆栈仿真没有明显的优势。 - Kirill V. Lyadvinsky
我认为这里的问题不在于递归算法是否总能被转化为迭代算法（答案是肯定的[1]）。 - Hardest
14

回应阿克曼函数答案, 这是一个很简单的将调用栈转换成真正的堆栈问题。这也展示了迭代版本的一个好处。

在我的平台上(Python 3.1rc2/Vista32)，迭代版本可以正确计算ack(3,7)=1021，而递归版本则导致栈溢出。注意：在另一台不同机器上的python 2.6.2 /Vista64上没有发生栈溢出，所以似乎非常依赖于平台。

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

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
我假设“append”实际上是“push”吗？ - Erich Mirabal
嗯，这是一个在 Python 中的列表呢。 - Jimmy
非递归实现和递归实现之间有何区别？换句话说，使用递归是否会提高性能或可读性？ - Aaron Hull
9
14
计数器：“阿克曼函数也可以使用康威链接箭头符号的方式进行非递归表示”（参见维基百科）。 - Marc Gravell
4
有趣。阿克曼函数不是原始递归函数：http://en.wikipedia.org/wiki/Primitive_recursive_function。根据该页面，具备基本算术、比较和有限循环功能的语言无法表达此类型的函数。但如果加入WHILE或GOTO，则又变成可图灵完备的了。 - Erika
2
请查看我在https://dev59.com/0nNA5IYBdhLWcg3wF5uO#1095538的回答。 - Jimmy
6
我认为区分那些“数学”定义涉及递归形式的问题和那些只能通过递归计算的问题是很重要的。你可以使用非递归编程形式计算Ackermann函数，但是你必须为每次迭代存储状态。 - LBushkin
1
@LBushkin 我完全同意。 - LB40
显示剩余5条评论
8

您可以定义一个没有递归的图灵机（对吗？）因此递归不是语言成为图灵完备所必需的。

在计算语言学中，图灵机高于基于堆栈的自动机，因为它可以模拟那些自动机（带子可以用作堆栈）。 - fortran
7
在编程中，递归实际上是迭代的一种特殊情况 - 它使用调用栈作为一种特殊的存储状态的手段。您可以将任何递归方法重写为迭代方法。它可能更复杂或不太优雅，但它是等效的。
在数学中，有一些问题需要使用递归技术才能得出答案 - 例如找到根（牛顿法），计算质数，图形优化等。然而，即使在这里，也只是一个如何区分“迭代”和“递归”的问题。
编辑：正如其他人指出的那样，存在许多定义是递归的函数 - 例如Ackermann函数。然而，这并不意味着它们不能使用迭代构造进行计算 - 只要您拥有图灵完备的操作集和无限的内存。
4

所有非NP完全问题都可以仅使用顺序、决策和迭代来解决。虽然递归通常会极大地简化问题，但不应该需要它。

1
NP完全问题也可以解决，只是需要更长的时间。 - Ian
1
这个答案是错误的。不可判定问题不是NP完全问题（也不能通过迭代或递归来解决）。 - Paul
3

问题的解决取决于需要编写多少行代码...

使用递归和不使用递归列出C:\上的所有文件。当然，两种方法都可以实现，但一种方法会更简单易懂且易于调试。

在树中搜索可以是深度优先或广度优先。前者自然地使用递归来实现，但后者更自然地使用迭代方法来实现。 - David Rodríguez - dribeas
1

递归本质上只是一个堆栈，通过显式实现一个堆栈，你可以实现相同的结果。

这可能并不是特别令人满意的答案，但你需要提出更加具体的问题才能获得更好的答案。例如，理论指出，在计算机的级别中，如果你只有 while 循环而没有传统的 for 循环，那么可以解决的问题范围会有很大的差异。

我在其中加入了“传统”这个词，因为它们真正意味着迭代一定次数的循环，而 C 风格的 for (...;...;...) 循环则是 while 循环的伪装。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接