Class Notes (806,449)
United States (312,060)
COMPSCI 61A (130)
De Nero (43)
Lecture 17

# CS61A Lecture 17: Recursive Objects

3 Pages
65 Views

School
University of California - Berkeley
Department
Computer Science
Course
COMPSCI 61A
Professor
De Nero
Semester
Fall

Description
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

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.