[Tutor] recursion

[Danny Yoo]

On Thu, Feb 4, 2016 at 6:03 PM, noopy via Tutor <tutor at python.org> wrote:
> Hi,
>
> I just cannot get my head around the following code, maybe someone could
> explain it to me.

One thing to note: the function here is a generator, which is itself
an intermediate subject that's specific to Python.  Recursion is a
more general concept that's shared by a lot of other programming
languages.  Tackling generators at the same time as recursion may make
both subjects harder to learn at first.



You might want to consider a version of permutations that doesn't do
any generator-related stuff.  Here's a version of permutations that's
a regular function:

##############################################
def permutations(items):
    n = len(items)
    if n == 0:
        return [[]]
    else:
        allPerms = []
        for i in range(len(items)):
            for cc in permutations(items[:i] + items[i+1:]):
                allPerms.append([items[i]] + cc)
        return allPerms
##############################################

This version should be a bit easier to understand, since we don't have
to deal with generators at the same time.


Also, we often have the choice of defining what the function should do
for "small" base cases.  Zero isn't always the most comprehensible
case to start with.  If it helps to make the function simpler to
understand, start with a list of length 1 or 2.  You don't have to
make the function's basis something that doesn't make sense to you.

What should the answer to permutations(['x']) be, for example?

I think it should be:

    [['x']]

Do you agree?  Did you have something else in mind?


Another question:  What should the answer to permutations(['x', 'y']) be?


It's very easy to write code that's busy or using CPU cycles.  It's
harder to tell whether it's doing something right.  To solve that
problem, we should build up a repertoire of known good solutions:
they'll make great test cases.