Implementing Reversals
Reversal of collections can be coded either recursively or iteratively in Python, and as
functions or class methods. Example 18-23 is a first attempt at two simple reversal
functions.
Example 18-23. PP4E\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 res
Both reversal functions work correctly on lists. But if we try reversing nonlist sequences
(strings, tuples, and so on), 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 18-24 fix both problems by using generic sequence handling
techniques much like that of the prior section’s permutation utilities:
- reverse uses the not operator to detect the end of the sequence and returns the
empty sequence itself, rather than an empty list constant. Since the empty sequence
is the type of the original argument, the + operation always builds the correct type
sequence as the recursion unfolds. - ireverse makes use of the fact that slicing a sequence returns a sequence of the
same type. It first initializes the result to the slice [:0], a new, empty slice of
the argument’s type. Later, it uses slicing to extract one-node sequences to add to
the result’s front, instead of a list constant.
Example 18-24. PP4E\Dstruct\Classics\rev2.py
def reverse(list):
if not list: # empty? (not always [])
return list # the same sequence type
1398 | Chapter 18: Data Structures