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
 
Line 1: Line 1:
# best to solve 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()).  
+
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()).  
  
 
# Base case: L is empty. Then, the answer is 0  
 
# Base case: L is empty. Then, the answer is 0  
Line 9: Line 9:
 
     else:
 
     else:
 
         return len(L.pop()) + 1
 
         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

Latest revision as of 03:12, December 16, 2011

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
   else:
       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
Namespaces
Variants
Actions
Navigation
Toolbox
EECS @ UM
Tools