有没有时间你不会使用递归？ [英] is there ever a time you would not use recursion?

问题描述

我的大学实验室有问题;

I have a problem for a university lab;

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

这似乎是一个常见的面试问题，并且记录良好。

It seems to be a common interview question and well documented.

所以我使用递归方法用Java编写它并不太难，何时或为什么你选择不使用递归和什么这是最简单的方法吗？

So I've coded it with Java using a recursive method which wasn't too hard, when or why would you choose not to use recursion and what would be the easiest way of doing it?

我开始编写一个计数器，它会倒数到基数为6，然后输出会引用char和打印字符串。

I started to code a counter that would count down on base 6, the output would then reference char's and print the string.

谢谢，

推荐答案

是的，有很多有时我不会使用递归。递归不是免费的，它在堆栈空间中有成本，并且通常比其他一些资源更有限。在设置和拆除堆栈帧时，还有一个时间成本，无论多么小。

Yes, there are plenty of times I would not use recursion. Recursion is not free, it has a cost in stack space and that can often be a much more limited resource than some others. There's also a time cost, however small, in setting up and tearing down stack frames.

举例来说，大肆吹嘘的因子函数是我可能选择的函数对于数字很大的迭代方法。计算10000！使用：

By way of example, the much vaunted factorial function is one where I would probably opt for an iterative approach where the numbers were large. Calculating 10000! with:

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

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

will use 10,000 stack frames (assuming it's not optimised by the compiler into an iterative solution of course), quite a lot. The iterative solution:

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

将只使用一个堆栈框架而且只使用其他一些东西。

will use just the one stack frame and precious little else.

递归解决方案通常是更优雅的代码，但是你必须调整它的局限性你的环境。

It's true that recursive solutions are often more elegant code but you have to temper that with the limitations of your environment.

你的 carbon 例子是我实际上使用递归的例子：

Your carbon example is one where I would actually use recursion since:

• 它最多使用六个堆栈帧（字符串中每个字符一个）;和


• 它相对优雅，至少比六个嵌套循环和大量的相等检查要多得多。

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

For example the following Python code does the trick:

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

Of course, if your string can be 10K long, I'd rethink it, since that would involve a lot more stack levels but, provided you keep in low enough, recursion is a viable solution.

这篇关于有没有时间你不会使用递归？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！