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 17-21 is a first attempt at two simple reversal functions.
Example 17-21. PP2E\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, etc.) 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,
and 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 17-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 ...