有没有一段时间您不使用递归？

Question

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

编写一个简短的程序，输出使用字符“ c”，“ a”，“ r”，“ b”，“ o”和“ n”恰好一次形成的所有可能的字符串。

这似乎是一个常见的面试问题，并且有据可查。

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

我开始编写一个计数器，该计数器将从6开始递减计数，然后输出将引用char并打印字符串。

谢谢，

Answer 1

是的，很多时候我不会使用递归。递归 不是
免费的，它在堆栈空间上有成本，并且与其他资源相比，资源通常更为有限。设置和拆卸堆栈框架也要花费时间，无论多么小。

举例来说，倍受吹捧的阶乘函数就是我可能会选择一种迭代方法的函数，该函数的数目很大。计算10000！与：

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

将使用10,000个堆栈帧（假设编译器没有将其优化为迭代解决方案，当然）。迭代解决方案：

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长，我会重新考虑一下，因为这将涉及更多的堆栈级别，但是，如果保持足够低，则递归是一个可行的解决方案。