bad recursion, still works

iu2 israelu at elbit.co.il
Tue Jul 15 22:12:28 CEST 2008


On Jul 15, 9:30 pm, mdshe... at gmail.com wrote:
> On Jul 15, 2:59 pm, iu2 <isra... at elbit.co.il> wrote:
>
>
>
> > Hi,
>
> > I wrote this wrong recursive function that flattens a list:
>
> > def flatten(lst, acc=[]):
> >     #print 'acc =', acc, 'lst =', lst
> >     if type(lst) != list:
> >         acc.append(lst)
> >     else:
> >         for item in lst:
> >             flatten(item)
> >     return acc
>
> > a = [1, 2, [3, 4, 5], [6, [7, 8, [9, 10], 11], 12], 13, 14]
> > b = flatten(a)
> > print b
>
> > I was amazed to realize that it flattens the list alright. Why? 'acc'
> > should be an empty list on each invocation of flatten, but is seems to
> > accumulate anyway...
>
> When you say acc=[] in the function declaration, it binds acc to a
> particular list object, rather than to a concept of an empty list.
> Thus, all operations being performed on acc are being performed on the
> same list. If, after the sample code you provided, were to call
>
> c = flatten([15,16,17,[18,19]])
> print c
>
> you would get back the list [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
> 13, 14, 15, 16, 17, 18, 19].
>
> Mark Sherry

I still don't understand: In each recursive call to flatten, acc
should be bound to a new [], shouldn't it? Why does the binding happen
only on the first call to flatten?



More information about the Python-list mailing list