'is there ever a time you would not use recursion? [closed]

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,

javarecursion


Solution 1:[1]

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!

Solution 2:[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.

Solution 3:[3]

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

Solution 4:[4]

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

Solution 5:[5]

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

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Alex Feinman
Solution 2 Numenor
Solution 3 Branimir
Solution 4 Gadolin
Solution 5

Related Questions