有没有时间你不会使用递归？

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

Answer 2

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

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

如果算法的结构反映了底层问题的结构,那么最终会得到更易于理解的更简单的代码.不要仅仅因为你的CS201教授认为它是如此使用递归!凉!

Answer 3

只需使用循环,您将避免使用递归.通常避免递归,因为它使代码可读性降低,难以维护和调试.如果您的资源很少,因为paxdiablo说堆栈空间可能对您有价值,所以您也应该避免使用它.