Newbi Q: Recursively reverse lists but NOT strings?

Bruno Desthuilliers bdesth.quelquechose at
Wed Oct 17 00:12:46 CEST 2007

<OT>answering to Dmitri O.Kondratiev<OT>
> On Sunday 14 October 2007 5:06:19 pm Dmitri O.Kondratiev wrote:
>>The function I wrote (below) reverses lists all right:
>>def reverse(xs):
>>    if xs == []:
>>        return []
>>    else:
>>        return (reverse (xs[1:])) + [xs[0]]
>>>>>reverse ([1,2,3])
>>[3, 2, 1]
>>Yet when I try to reverse a string I  get:
>>>>>reverse ("abc")
>>  File "C:\wks\python-wks\", line 5, in reverse
>>    return (reverse (xs[1:])) + [xs[0]]
>>  File "C:\wks\python-wks\", line 5, in reverse
>>    return (reverse (xs[1:])) + [xs[0]]
>>  File "C:\wks\python-wks\", line 2, in reverse
>>    if xs == []:
>>RuntimeError: maximum recursion depth exceeded in cmp
>>What's wrong? Why recursion never stops?

Because an empty string doesn't compare equal to an empty list. So if xs 
is not a list, the test always fails, and you always go to the 'else' 

Now since in Python, most (and at least all builtins) empty containers 
and/or sequence types evals to false in a boolen context, there's an 
obvious fix to your function:

def reverse(xs):
   if xs:
     return xs
     return (reverse (xs[1:])) + [xs[0]]

Anyway, there's a much simpler solution:

   reverse = lambda x : x[::-1]

which is so simple it doesn't even justify a function call !-)

Oh, and, yes, while we're at it:

Help on class reversed in module __builtin__:

class reversed(object)
  |  reversed(sequence) -> reverse iterator over values of the sequence


More information about the Python-list mailing list