is there ever a time you would not use recursion?

Question

I have a problem for a university lab;

Write a short program that outputs all possible strings formed by using characters ‘c’, ‘a’, ‘r’, ‘b’, ‘o’, and ‘n’ exactly once.

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

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?

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

Thanks,

Answer 1

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.

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 the Python:

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

will attempt to use a whopping 10,000 stack frames (though Python will protect you against this). The equivalent 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.

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

• it uses at most six stack frames (one per character in the string); and
• it's relatively elegant, at least much more so than six nested loops and huge equality checks.

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")

producing:

abc
acb
bca
bac
cab
cba

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.

Answer 2

Use recursion when your data is inherently hierarchical/nested. Use iteration when your data is linear/flat.

In your case, there is a natural ordering you can impose on the combinations, so you can treat the data as linear, but if you view it as a tree you end up with the recursive approach.

If the structure of your algorithm reflects the structure of the underlying problem, you end up with simpler code that is easier to understand. Don't use recursion just because your CS201 professor thought it was So! Cool!

Answer 3

Just use a loop and you will avoid using recursion. Recursion is avoided generally because it makes the code less readable and harder to maintain and debug. If you have low resources as paxdiablo said stack space might be valuable for you so you should avoid using it then too.

Answer 4

Algorithms and Data Structures by Niklaus Wirth have a section "When not to use recursion", but recursion is useful programmer`s tool. I think that understanding recursion is "must" for a programmer.

You have a clever approach to permutation problem. It can be solved recursively (pseudocode):

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

When there is plenty of invocations of recursion then your stack may explode leaving you with StackOverflowError. The good example is calculation of Fibonacci numbers (or Hanoi towers problem) with basic recursion you will not be able to calculate many of those numbers. Which you will be able by using of non recurring version. Basically recursion creates nice looking solution and this is a virtue. You may still have good working recursion solution by using tail recursion

Answer 6

As the people above have written, recursion is not always the optimal solution (function calls may be expensive and they consume the stack unless the compiler can optimize tail recursion away). However, it's particularly suited to such problems as yours.

While theoretically it's possible to express each recursive algorithm in terms of iteration (ex. by manually simulating the call stack with an array), sometimes the equivalent iterative solution is less elegant. Here is a sample:

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()