Home Original page

Recursion and Variable Scope

mudpyr8 mudpyr8 at yahoo.com
Fri Sep 7 18:07:38 EDT 2001 
Wow! Thank you so much. That was very instructive. I new there was one
little piece I was missing that I just couldn't find on my own.

I really appreciate the time you took to explain everything. That was
an incredible help.

- Shane

"Alex Martelli" <aleax at aleax.it> wrote in message news:<9n9vln072d at enews1.newsguy.com>...
> "mudpyr8" <mudpyr8 at yahoo.com> wrote in message
> news:d9f7d05e.0109061911.6bdcda3f at posting.google.com...
> > I'm writing a simple function. It is recursive. Here's the code:
> >
> > ##########################
> > def generate(sides, dice, roll):
> > if dice > 0:
> > for x in range(sides):
> > roll.append(x+1)
> > generate(sides, dice - 1, roll)
> > roll.pop()
> > else:
> > print roll
> > ##########################
> >
> > When calling it: generate(4, 2, [])
> > will generate output of 16 pairs of values, 1-4 each. However, I
> > cannot get that result stored in an object; I can only print it.
> >
> > The last line is the tricky part. Where it says   # print roll #   I
> > want it to do something like:   # rolls.append(roll) #  .
> > Unfortunately, creating a variable   # rolls = [] #   outside of the
> > function definition, and even stating   # global rolls #   on the
> > first line of the block doesn't seem to matter.
> 
> More precisely, if you say:
>     rolls.append(roll)
> you're adding to tolls a reference to the OBJECT to which
> roll also refers, *NOT* a copy or snapshot of the way that
> object is *currently* made up.  Python doesn't do copies
> or snapshots behind your back: if you want a copy, you ask
> for a copy.  So, to clarify, a slight mod to your code:
> 
> rolls = []
> 
> def generate(sides, dice, roll):
>     if dice > 0:
>         for x in range(sides):
>             roll.append(x+1)
>             generate(sides, dice - 1, roll)
>             roll.pop()
>     else:
>         print roll
>         rolls.append(roll)
> 
> (no "global rolls" needed: we are not BINDING rolls, so
> the compiler knows it can't be local -- we just call a
> method on rolls, and it's irrelevant to this purpose that
> the method is a mutator rather than just an accessor:-).
> 
> Now, running this:
> 
> D:\>python -i ro.py
> Alternative ReadLine 1.4 -- Copyright 2001, Chris Gonnerman
> >>> generate(4,2,[])
> [1, 1]
> [1, 2]
> [1, 3]
> [1, 4]
> [2, 1]
> [2, 2]
> [2, 3]
> [2, 4]
> [3, 1]
> [3, 2]
> [3, 3]
> [3, 4]
> [4, 1]
> [4, 2]
> [4, 3]
> [4, 4]
> >>> rolls
>  [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
> >>>
> 
> and just for clarity, if we now write in this interactive session:
> 
> >>> rolls[0].append('x')
> >>> rolls
> [['x'], ['x'], ['x'], ['x'], ['x'], ['x'], ['x'], ['x'], ['x'], ['x'],
> ['x'], ['
> x'], ['x'], ['x'], ['x'], ['x']]
> >>>
> 
> see?  rolls has 16 references to the SAME list object -- and, no
> surprise about that, since we've always appended to rolls a
> reference to the same list object each time.
> A list object is mutable, so, as we mutate the list object (to
> which 'roll' refers in function generate), all references see
> the current (mutated) version.  Clear so far...?
> 
> So, simplest is to append a COPY of roll to rolls, e.g. changing
> the very last line of my version of generate to:
>         rolls.append(roll[:])
> now python -i ro.py gives us the same output (same print
> statements get executed) but then checking out interactively
> what's left in global variable rolls we see:
> 
> >>> rolls
> [[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3,
> 2],
>  [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]]
> 
> which, I think, is what you desire.
> 
> 
> > I've tried to wrap my mind around this but am stuck. I need to perform
> > further manipulation on the results, but have no object with which to
> > do so. I know I could write to a file (maybe, if the file handle works
> > within the recursion) and then read it but that seems like a waste of
> > time.
> 
> Yes, writing to a file IS a way to ensure a copy of the object
> is made at that point (note that *pickling* to a pickler object
> would not ensure that: if you pickle a mutable object to the
> same pickler repeatedly, it's NOT "snapshotted" each time, you
> get when unpickling all references to the value the object had
> when FIRST pickled!), but a very round-about one indeed.
> 
> You want a copy, just ask for a copy -- a "full list slice"
> roll[:] will do, or import copy and use copy.copy(roll) if
> you need better polymorphism (which I don't think you do
> here) or prefer the more explicit, readable form (but [:]
> is very idiomatic to experienced Pythmen!-).
> 
> I hope this proves instructive regarding the crucial "objects
> and references" underpinning of Python.  Still, there are of
> course alternate approaches to your specific task than having
> all those appends and pops from roll and recursion too.  My
> personal favourite is looking at the lists you're generating
> as rather transparent "base-N numbers of X digits each" where
> X is dice and N is sides (you have a +1 to each digit, but
> that's not crucial of course:-).  So just count from 0 to
> N**X-1 with digit rollover, and you don't really need the
> auxiliary list roll either:
> 
> def gen(sides, dice):
>     results = []
>     current = dice*[1]
>     while 1:
>         results.append(current[:])
>         n = dice - 1
>         while n>=0:
>             current[n] += 1
>             if current[n]<=sides: break
>             current[n] = 1
>             n -= 1
>         else: break
>     return results
> 
> Now:
> 
> >>> gen(4,2)
> [[1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [3, 1], [3,
> 2],
>  [3, 3], [3, 4], [4, 1], [4, 2], [4, 3], [4, 4]]
> 
> Personally, I find it clearest to frame such enumeration
> problems as "counting in a certain base" (or sequence of
> bases, if the dice have different number of sides), but
> that's pretty much up to individual taste, of course;
> there's no substantial performance difference.  (in a
> few test runs with 6 6-sided dice gen tends to be 20%
> or 30% faster on my box, i.e pretty much in the "don't
> worry about it" field:-).  I like gen because it's more
> flexible -- I can easily optimize by preallocation...:
> 
> def gen1(sides, dice):
>     results = [0]*(sides**dice)
>     current = dice*[1]
>     i = 0
>     while 1:
>         results[i] = current[:]
>         i += 1
>         n = dice - 1
>         while n>=0:
>             current[n] += 1
>             if current[n]<=sides: break
>             current[n] = 1
>             n -= 1
>         else: break
>     return results
> 
> for a further 30%-or-so speedup -- and now gen1 is
> being almost twice as fast as generate, which may
> be already in the useful-speedup zone in some cases
> (those in which this generation is the bottleneck
> of some important operation of your program).  Or,
> when I want flexibility instead, I can more easily
> wrap gen up as a class with a __getitem__, so it
> can be used as the sequence in a for statement (in
> Python 2.2 this is not so important, thanks to
> generator iterators, but sometimes it may be useful
> to keep compatibility with older Python versions).
> 
> Generalizing to differently-sided dice is easier --
> imagine sides is a sequence of dice items, each
> a number giving the # sides of that specific die,
> then all the changes you need (e.g. to gen1) are:
> 
> def gen2(sides, dice):
>     import operator
>     assert len(sides)==dice
>     results = [0]*reduce(operator.mul,sides)
>     current = dice*[1]
>     i = 0
>     while 1:
>         results[i] = current[:]
>         i += 1
>         n = dice - 1
>         while n>=0:
>             current[n] += 1
>             if current[n]<=sides[n]: break
>             current[n] = 1
>             n -= 1
>         else: break
>     return results
> 
> basically just testing vs sides[n] rather
> than a single number 'sides', and a tiny bit
> more work at startup for pre-allocation.
> 
> But I'm sure the recursive approach must have
> some advantages too, if it's clearer to you or
> more flexible along axes that matter to you.
> 
> 
> Alex
More information about the Python-list mailing list