[Tutor] Recursion

[Daniel Yoo]

On Wed, 6 Jun 2001, Glen Wheeler wrote:

>   For example, if I wanted to get all the permutations of a set
> ['a','b'] taken three at a time, I would write this :
> 
> >>> c = []
> >>> s = ['a', 'b']
> >>> for i1 in range(len(s)):
> ...  for i2 in range(len(s)):
> ...   for i3 in range(len(s)):
> ...    c.append([s[i1], s[i2], s[i3]])
> ... 
> >>> for item in c: print item
> ... 
> ['a', 'a', 'a']
> ['a', 'a', 'b']
> ['a', 'b', 'a']
> ['a', 'b', 'b']
> ['b', 'a', 'a']
> ['b', 'a', 'b']
> ['b', 'b', 'a']
> ['b', 'b', 'b']
> 
>   Which is all well and good, but when I want to take them n at a time
> I need more for loops.  Thus I thought 'Hmmm, I could get a function
> which calls itself n times...that would work!' - but I'm just too
> green with this sort of programming for it to happen for me.

Hello Glen!

To see the recursion, we should look at some small cases of the problem
first.  As background for the others: the idea of recursion is to see a
relationship between the "big" version of a problem and a slightly smaller
version.  By seeing this relationship, we may be able to solve the big
problem by taking advantage of the solution for the small one.


In this problem, we're measuring bigness by 'n at a time'.  The bigger 'n'
gets, the larger the problem.  Let's take a really close look at what the
program should do when n is equal to 1, 2, and 3.  Once we do this, things
might look clearer (or more blurry, depending on how long we strain our
eyes... *grin*)


We know that taking the one_at_a_time() on this list ['a', 'b'] should
look like:

    [ ['a'],
      ['b'] ]

Let's pretend we have that function to play with.  We can imagine what the
result of two_at_a_time() looks like:

    [ ['a', 'a'],
      ['a', 'b'],

      ['b', 'a'],
      ['b', 'b'] ]


I'm intensionally printing two_at_a_time()'s result in 2 visually distinct
blocks because, if we look at this for a little bit, we might see a small
pattern.  In order to get two_at_a_time(), all we need to do is take every
element in one_at_a_time, and plunk either 'a' or 'b' in front.  This can
be written as:


###
def two_at_a_time(L):
    source = one_at_a_time(L)
    c = []
    for x in L:
        for s in source:
            c.append([x] + s)
###


Ok, let's look at three_at_a_time() and see if there's a relationship
between it and two_at_a_time:


    [ ['a', 'a', 'a'],
      ['a', 'a', 'b'],
      ['a', 'b', 'a'],
      ['a', 'b', 'b'],

      ['b', 'a', 'a'],
      ['b', 'a', 'b'],
      ['b', 'b', 'a'],
      ['b', 'b', 'b'], ]


Same idea: let's use two_at_a_time() to solve three_at_a_time()!  The
definition for three_at_a_time() will eerily familiar...

###
def three_at_a_time(L):
    source = two_at_a_time(L)
    c = []
    for x in L:
        for s in source:
            c.append([x] + s)
###


This should give you enough to write n_at_a_time().  If you have any
questions, please feel free to ask.  Good luck!