有没有什么时候你不会使用递归？

Question

我有一个关于大学实验室的问题；

输出一次使用字符“c”、“a”、“r”、“b”、“o”和“n”形成的所有可能的字符串。

编写一个简短的程序，仅 是一个常见的面试问题并且有据可查。

因此，我使用 Java 使用递归方法对其进行了编码，这并不太难，什么时候或为什么选择不使用递归以及最简单的方法是什么？

我开始编写一个以 6 为底数的计数器，然后输出将引用 char 并打印字符串。

谢谢，

Answer 1

是的，很多时候我不会使用递归。递归不是免费的，它会消耗堆栈空间，并且与其他资源相比，这通常是更有限的资源。设置和拆除堆栈框架也会产生时间成本，无论时间成本有多小。

举例来说，在备受推崇的阶乘函数中，当数字很大时，我可能会选择迭代方法。计算10000！使用Python：

def factorial (n):
    if n = 1: return 1
    return n * factorial (n-1)

将尝试使用多达10,000个堆栈帧（尽管Python会保护你免受这种情况的影响）。等效的迭代解决方案：

def factorial (n):
    r = 1
    while n > 1:
        r = r * n
        n = n - 1
    return r

将仅使用一个堆栈框架，而几乎不使用其他资源。

确实，递归解决方案通常是更优雅的代码，但您必须根据环境的限制来调整它。

您的 Carbon 示例是我实际使用递归的示例，因为：

• 它最多使用六个堆栈帧（字符串中的每个字符一个）；而且
• 它相对优雅，至少比六个嵌套循环和巨大的相等检查要优雅得多。

例如，下面的Python代码就可以解决这个问题：

def recur (str, pref = ""):
    # Terminating condition.

    if str == "":
        print pref
        return

    # Rotate string so all letters get a chance to be first.

    for i in range (len (str)):
        recur (str[1:], pref + str[:1])
        str = str[1:] + str[:1]

recur ("abc")

生成：

abc
acb
bca
bac
cab
cba

当然，如果你的字符串可以有10K长，我会重新考虑它，因为这会涉及更多的堆栈级别，但是，只要你保持足够低的水平，递归就是一个可行的解决方案。

Answer 2

当数据本质上是分层/嵌套的时，请使用递归。当数据是线性/平坦时使用迭代。

在您的情况下，您可以对组合施加自然排序，因此您可以将数据视为线性，但如果您将其视为树，则最终会采用递归方法。

如果算法的结构反映了底层问题的结构，那么您最终会得到更简单、更容易理解的代码。不要仅仅因为你的 CS201 教授认为递归就使用递归 所以！凉爽的！

Answer 3

只需使用循环即可避免使用递归。通常要避免递归，因为它会降低代码的可读性并且更难以维护和调试。如果你的资源很少，正如 paxdiablo 所说，堆栈空间可能对你很有价值，所以你也应该避免使用它。

Answer 4

Niklaus Wirth 的算法和数据结构 有一节“何时不使用递归” ”，但是递归是有用的程序员工具。我认为理解递归对于程序员来说是“必须”的。

您对排列问题有一个聪明的方法。可以递归地解决（伪代码）：

private void PermutationsRecursive(string prefix, string s)
{
    int N = s.Length;

    if (N > 0)
        for (int i = 0; i < N; i++)
            PermutationsRecursive(prefix + s[i], s.Substring(0, i) + s.Substring(i + 1, N - i - 1));
    else
        WriteLine(prefix);
}

PermutationsRecursive("", "carbon");

Answer 5

当有大量递归调用时，您的堆栈可能会爆炸，从而导致 StackOverflowError。一个很好的例子是使用基本的斐波那契数（或河内塔问题）计算
递归你将无法计算其中的许多数字。您可以通过使用非重复版本来实现。基本上，递归创建了漂亮的解决方案，这是一个优点。通过使用尾递归，您仍然可以拥有良好的递归解决方案

Answer 6

正如上面的人所写的，递归并不总是最佳解决方案（函数调用可能很昂贵，并且它们会消耗堆栈，除非编译器可以优化尾递归）。但是，它特别适合解决像您这样的问题。

虽然理论上可以用迭代来表达每个递归算法（例如，通过使用数组手动模拟调用堆栈），但有时等效的迭代解决方案不太优雅。这是一个示例：

text = 'carbon'
n = len(text)
for permutation_i in range(factorial(n)):
    free_letters = list(text)
    divisor = 1
    for character_i in range(n, 0, -1):
        letter = free_letters.pop(permutation_i//divisor%character_i)
        print(letter, end='')
        divisor *= character_i
    print()