Reversing Sequences
Reversal of collections is another typical operation. We can code it either recursively or iteratively in Python, and as functions or class methods. Example 20-21 is a first attempt at two simple reversal functions.
Example 20-21. PP3E\Dstruct\Classics\rev1.py
def reverse(list): # recursive
if list == []:
return []
else:
return reverse(list[1:]) + list[:1]
def ireverse(list): # iterative
res = []
for x in list: res = [x] + res
return resBoth reversal functions work correctly on lists. But if we try
reversing nonlist sequences (strings, tuples, and so on) we’re in
trouble: the ireverse function
always returns a list for the result regardless of the type of
sequence passed:
>>>ireverse("spam")
['m', 'a', 'p', 's']Much worse, the recursive reverse version won’t work at all for
nonlists—it gets stuck in an infinite loop. The reason is subtle: when
reverse reaches the empty string
(""), it’s not equal to the empty
list ([]), so the else clause is selected. But slicing an
empty sequence returns another empty sequence (indexes are scaled):
the else clause recurs again with
an empty sequence, without raising an exception. The net effect is
that this function gets stuck in a loop, calling itself over and over
again until Python runs out of memory.
The versions in Example 20-22 fix both problems by using generic sequence handling techniques:
reverseuses thenotoperator to detect the end of the sequence and returns the empty sequence itself, rather than an empty list constant. ...