Is there ever a time when you will not use recursion?

Question

I have a problem for a university laboratory;

Write a short program that displays all the possible lines formed using the characters "c", "a", "r", "b", "o" and "n" exactly once.

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

So, I encoded it using Java using a recursive method that was not too complicated , when or why did you decide not to use recursion and what would be the easiest way to do this?

I started to encode a counter that would pay attention to base 6, then the result would refer to char and print the line.

Thank,

Answer 1

Yes, there are many times, I would not use recursion. Recursion is not free, it has costs in the stack space and can often be a much more limited resource than some others. There is also a temporary cost, albeit small, when setting up and breaking stack frames.

As an example, a highly praised factorial function is one where I would probably prefer an iterative approach when numbers were large. Computing 10000! with:

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

will use 10000 stack frames (provided that it is not optimized by the compiler in an iterative solution, of course), quite a lot. Iterative solution:

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

will use only one stack frame and some more precious.

, , .

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

, . - , . , paxdiablo , , .

Answer 3

, /. , /.

, , , , .

, , . , CS201 , ! !

Answer 4

Niklaus Wirth " ", - . , "" .

permutation. ():

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

, , StackOverflowError. ( ) . . , .

Answer 6

, ( , , ). , .

Although it is theoretically possible to express each recursive algorithm in terms of iteration (for example, manually simulating a call stack with an array), sometimes the equivalent iterative solution is less elegant. Here is an example:

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