In-class notes for 03/05/2014

CS 121B (CS1), Spring 2014

• Homework assignment

• Quizzes returned

• Prof Richey on Friday. Machine learning: programming a computer to make decisions, given lots of data.

Submitted questions on assignments and technology

• Solution to the double problem for images

• Solution to Recursion problem 10d

  (Note that the Sprig example repeats without a loop.)

Upcoming

• Homework 11

  • Recall nested list representation for trees.

    Example:

    

    
    
    lis = ["Elizabeth II", 
    	"Charles", 
    	["Anne", ["Peter", "Savannah", "Isla"], ["Zara, "Mia"]]
    	"Andrew",
    	"Edward"]
    

    How could you index lis in order to return Elizabeth's third child? Anne's first child? Anne's children?

    HW problems to write functions that return certain nodes in a tree.

    Note: Use guards to determine whether a desired relative exists in the tree; return False if it doesn't.

• Read online text: Strings
  submit at least one reading question by 9am before the next class meeting

• Quiz on Friday. See below for topics.

Recursion

• Recursion: A function calls itself in its own definition

• Sprig example

• Solving problems with recursion

  • List cases

  • Reason from the spec.
        E.g., the spec tells the value from the recursive call
        Use spec to check types of the return values

  • Use #assert comments at strategic locations in the code
        Milestones in the reasoning

• Example: countElements()

  countElements One argument: A Python3 list Return: A non-negative integer, the number of elements in arg1

  Example call:

      countElements([1, 'a', 2]) --> 3
      countElements([]) --> 0
  

  • List cases

    • empty list, i.e., []

    • non-empty list (at least one element), e.g., [1, 'a', 2]

  • Reason from the spec.

    E.g., the spec tells the value from the recursive call

    If lis is a list, what is the meaning of a call countElements(lis[1:])?

    Use spec to check types of the return values, e.g., empty-list case returns 0, not "" or [] in code box below.

  • Use #assert comments at strategic locations in the code

    Milestones in the reasoning

    E.g.,

        def countElements(lis):
    	if lis == []:
    	    return 0
    	# assert:  at least one element in lis
    	else:
    	    ______
    

  Solution

Exercises

---

1. Exercise: Write a function that produces a list of doubles of elements in a list of numbers, using recursion

   double One argument: A list of numbers Return: A list of numbers, whose elements are twice the corresponding elements of the list arg1

   Example call:

       double([4, 7, -1.5]) --> [8, 14, -3.0]
       double([]) --> []
   

   Hints:

   • Use the concatenation operator + assemble the answer.

   • As before: use if to handle the empty-list case separately; no accumulator; use a slice.

---

2. Exercise: Write a function whose return value replaces particular value in a list with another value, using recursion

   replace 3 arguments: Any two Python3 values and any Python3 list Return: A list, whose elements are the same as the elements of the list arg3, except with each occurrence of arg1 replaced arg2.

   Example calls:

       replace ('a', 77, [4, 'a', 1]) --> [4, 77, 1]
       replace (5, 8, [5, 5, 0, 5, 7]) --> [8, 8, 0, 8, 7]
       replace (5, 8, []) --> []
   

   Hints:

   • This problem needs three cases:
     • empty list
     • first element matches arg1
     • first element doesn't match arg1
     Use if/elif/else (or nested if/else to program for each case separately

   • As before, use concatenation operator, slice, etc.

   • Be sure to include the first two arguments in your recursive calls

---

3. Exercise: Write a function whose return value is the sum of the integer elements in a list using recursion and no loops.

   sumIntegers One argument: Any Python3 list. Return: An integer, the sum of all integer elements in arg1.

   Example calls:

   sumIntegers([4, 'a', 5]) --> 9
   sumIntegers([4, ['a', 5]]) --> 4
   sumIntegers(['hello', 'world']) --> 0
   sumIntegers([]) --> 0
   

---

Three ways to understand recursion

• Problem solving, with logic, specs, asserts

  Stopping conditions:

  • Every recursive call uses smaller data

  • Smallest-data case(s) implemented without recursion

  E.g.,

      def sumList(numlist):
  	if numlist == []:
  	    return 0
          # assert: there is at least one element in numlist
  	else:  
  	    return numlist[0] + sumList(numlist[1:])
  

• Code patterns. Some common patterns in recursive code:

  • if lis == []:

  • ______ + func(lis[1:])

  • 
        if ______:
            return ______
        
        # assert: ______
        elif ______:
            return ______
        
        # assert: ______
        elif ______:
            return ______
        
        # assert: ______
        else:
            return ______
    
        

• Tracing.

  Example:

      def sumList(numlist):
  	if numlist == []:
  	    return 0
          # assert: there is at least one element in numlist
  	else:  
  	    return numlist[0] + sumList(numlist[1:])
  

  Trace of call sumList([4, 8, 9])
  

Submitted questions on readings

• Summary of strings chapter

To study for quiz

• Functions with if, conditional accumulators; writing predicates

• Image processing

• while loops