Newbi Q: Recursively reverse lists but NOT strings?

Bruno Desthuilliers bdesth.quelquechose at free.quelquepart.fr
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\reverse.py", line 5, in reverse
>>    return (reverse (xs[1:])) + [xs[0]]
>>  File "C:\wks\python-wks\reverse.py", line 5, in reverse
>>    return (reverse (xs[1:])) + [xs[0]]
>>  File "C:\wks\python-wks\reverse.py", 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' 
branch.

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
   else:
     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
"""

HTH



More information about the Python-list mailing list