bad recursion, still works

[mdsherry at gmail.com]

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