Find all permutations of string using recursion

Question

Background: I am somewhat new to programming and only two weeks into learning Python. Currently trying to improve my understanding of recursion, which has been a tough concept for me to implement.

Question: Is this a proper implementation of recursion or just an iterative approach with recursive flare? Or maybe neither? Looking for any tips/suggestions, not necessarily just the "correct" solution.

Code:

import math
def get_permutations(sequence):
    '''
    Enumerate all permutations of a given string

    sequence (string): an arbitrary string to permute. Assume that it is a
    non-empty string.  

    Returns: a list of all permutations of sequence

    '''
    if len(sequence) == 1:
        return list(sequence)
    else:
        char_to_insert = sequence[:1] 
        remainder = sequence[1:] 
        sub_permutations = get_permutations(remainder) 
        permutations = []
        for permutation in sub_permutations: 
            str_len = len(permutation)
            for i in range(0, str_len + 1): 
                front = permutation[:i]
                back = permutation[i:]
                permutations.append(front + char_to_insert + back)
        return permutations

Answer 1

It's fine to reinvent the wheel. Overheated comments to the contrary, it's perfectly fine to use classic algorithms as a vehicle to practice your coding skills. Just be aware, if you didn't know already, that itertools.permutations does exactly what you need. Using that function as a reference point, your code is producing correct results -- which is great. [The lone exception is your handling of empty inputs, which you explicitly declare out-of-scope. For details on that topic, see this question.] In addition to working correctly, your code is well organized, includes a docstring, uses communicative variable names, and is not too difficult to read and understand. That is a good start on your Python journey.

Consider yielding rather than returning a list. Because permutations scale so rapidly, this is the kind of situation where implementing a generator makes a lot of sense. It allows a caller, for example, to ask for an impossibly large permutation, consume some of its emitted data, and then stop consuming.

Strive for more intuitive implementations. My primary critique, and it's a mild one, is that your algorithm is not nearly as intuitive as others I've seen for permutations. A key skill in programming is recognizing when your implementation is less readable and more complicated that it ought to be. I'm not entirely certain how one acquires this skill; it's one of those "I know it when I see it" phenomena. In any case, the code in the illustration below has several advantages over your implementation: (1) simpler algorithm and less code; (2) comments that wrap an intuitive narrative around the algorithm; (3) a variable naming scheme that helps the reader understand the relevant parts (a collection of xs, the current x, and all of the other_xs); and (4) an implementation that emits the permutations in "lexicographic order according to the order of the input iterable", which is handy for testing and checking (the quote comes from the documentation for itertools.permutations).

def get_permutations(xs):
    if len(xs) == 1:
        yield xs[0]
    else:
        # Every X should get a chance to be the first.
        for i, x in enumerate(xs):
            # Yield X plus each permutation of the other Xs.
            other_xs = xs[0 : i] + xs[i + 1 : None]
            for p in get_permutations(other_xs):
                yield x + p

Next steps. One addition would be to correctly handle empty sequences or raise a ValueError if given one. Along a different track would be to generalize the function to handle any iterable as input. The latter is more challenging because it means we cannot use things like len(xs), xs[0], or xs[0 : i].