CS61A Lecture 17: Recursive Objects

3 Pages
Unlock Document

University of California - Berkeley
Computer Science
De Nero

Special Method Names in Python Certain names are special (or "magic") because have built-in behavior. Names start and end with two underscores __init__ Method invoked automatically when object constructed __len__ Method invoked by built-in len function s = (3, 4, 5) s.__len__() = 3 __getitem__ Method invoked for element selection: sequence[index] s = (3, 4, 5) s.__getitem__(2) = 5 __repr__ Method invoked to display object as string s = (3, 4, 5) print(s.__repr__()) = (3, 4, 5) Recursive List Class A tuple can contain another tuple as an element Pairs are sufficient to represent sequences of arbitrary length Recursive list representation of sequence 1, 2, 3, 4: Recursive lists are recursive: rest of list is a list Now, implement same behavior with class Rlist: Abstract data type (old): rlist(1, rlist(2, rlist(3, rlist(4, empty_rlist)))) Rlist class (new): Rlist(1, Rlist(2, Rlist(3, Rlist(4)) class Rlist: class EmptyList: def __len__(self): return 0 empty = EmptyList() def __init__(self, first, rest=empty): assert type(rest) is Rlist or rest is Rlist.empty self.first = first self.rest = rest def __getitem__(self, index): if index == 0: return self.first else: return self.rest[index-1] def __len__(self): return 1 + len(self.rest) def __repr__(self): return rlist_expression(self) How to print out Rlist: def rlist_expression(s): """Return a string that would evaluate to s.""" if s.rest is Rlist.empty: rest = '' else: rest = ', ' + rlist_expression(s.rest) return 'Rlist({0}{1})'.format(s.first, rest) Recursive List Processing Recursive list processing almost always involves recursive call on rest of list def extend_rlist(s1, s2): """Return a list containing the elements of s1 followed by those of s2. >>> extend_rlist(s.rest, s) Rlist(2, Rlist(3, Rlist(1, Rlist(2, Rlist(3)))))
More Less

Related notes for COMPSCI 61A

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.