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.

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)

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.

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

• it uses at most six stack frames; and
• it's relatively elegant, at least much more so than six nested loops and huge equality checks.

Answer 2

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 3

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

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!