Skip to Main Content
Programming Python, 3rd Edition
book

Programming Python, 3rd Edition

by Mark Lutz
August 2006
Intermediate to advanced content levelIntermediate to advanced
1600 pages
51h 46m
English
O'Reilly Media, Inc.
Content preview from Programming Python, 3rd Edition

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 res

Both 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:

  • reverse uses the not operator to detect the end of the sequence and returns the empty sequence itself, rather than an empty list constant. ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Learning Python, 3rd Edition

Learning Python, 3rd Edition

Mark Lutz

Publisher Resources

ISBN: 0596009259Supplemental ContentErrata Page