F. len(L): returns the number of objects in mylist.

From EECS 182
F. len(L): returns the number of objects in mylist.
Jump to: navigation, search

it is best to try to solve it recursively because the answer is trivial if the mylist object is empty and mylist is a recursive structure (a mylist object consists of mylist.pop() + mylist.last()).

  1. Base case: L is empty. Then, the answer is 0
  2. Non-base case: Decompose L into L.pop() and L.last(). L.pop() is now a smaller list. Assume that len works on that (recursive step). Can we construct the answer if we knew len(L.pop())? The answer is yes. We simply have to add 1 to it to get the answer. So, the answer will be len(L.pop()) + 1.

def len(L):

   if (L.isempty()):
       return 0
       return len(L.pop()) + 1

Actually, an iterative solution is also possible, but the above is more elegant. An iterative solution would use pop() repeatedly and check if the resulting list becomes empty, counting along the way.

def len(L):
      count = 0
      M = L
      while (not isempty(M)): 
            M = M.pop()
            count = count + 1
      return count
Personal tools