The permutation utilities of the prior section are useful in a variety of applications, but there are even more fundamental operations that might seem prime candidates for automation. Reversing and sorting collections of values, for example, are core operations in a broad range of programs. To demonstrate coding techniques, and to provide examples that yield closure for a recurring theme of this chapter, let’s take a quick look at both of these in turn.
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
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:
reverse reaches the empty
""), 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): ...