Recursive algorithms anyone?

[Tim Peters]

[Kirby Urner]
> How to implement in Python the classic thing of
> adding k to every item in a list.  Except a list
> may contain other lists to arbitary depth?

Something you'll probably never do in Python again <0.9 wink>.

> I say classic because it's the kind of thing you
> do in computer science 101.
>
> E.g.  >>> additem(1,[1,2,[3,4,[5,6]],7])
>       [2,3,[4,5,[6,7]],8]
>
> Here's the Scheme solution:
>
> (define (additem items k)
>   (cond ((null? items) null)
>         ((not (pair? items)) (+ items k))
>         (else (cons (additem (car items) k)
>                     (additem (cdr items) k)))))
>
>
> My best Python attempt so far:
>
>  >>> def additem(items, k):
>  	 if not type(items) == type([]):  return items + k
> 	 if len(items)==0: return []
>          return [additem(items[0],k)] + additem(items[1:],k)
>
>  >>> additem([[9,8],1,2,3,4,[1,2, [5,6]]],1)
>  [[10, 9], 2, 3, 4, 5, [2, 3, [6, 7]]]
>
> But maybe there's a better solution?

Depends on what's meant by "better".  The Python there isn't idiomatic, as
the natural way to process sequences in Python is via a "for" loop, not
recursion.  So 99 of 100 Pythonistas would first write something like this:

from types import ListType

def additem(items, k):
    result = []
    for x in items:
        if type(x) is ListType:
            result.append(additem(x, k))
        else:
            result.append(x + k)
    return result

"for x in whatever" says "I'm marching over a list" in Python like "(cond
((null? whatever) ...) ((pair? whatever) ...) (else ...))" says "I'm
marching over a list" in Scheme.  Get used to that, and the Python way puts
a lot less strain on your mental pattern-matcher <wink>.

Exercise:  now write a version in each language that modifies the list *in
place* instead of constructing a new list.  Define beforehand what the
desired outcome is for:

    x = [1, 2]
    y = [x, x]
    additem(y, 42)

Then do it all over again picking "the other" answer <heh>.

teasingly y'rs  - tim