1
h13
CS8 F18
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h13: Perkovic 10.1 and 10.2 (Recursion)

ready? assigned due points
true Tue 11/27 08:00AM Wed 12/05 09:00AM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE.
There is NO MAKEUP for missed assignments, and you may not submit work in advance, or on behalf of another person.
In place of that, we drop the four lowest scores (if you have zeros, those are the four lowest scores.)

Please:

  • No Staples.
  • No Paperclips.
  • No folded down corners.

Read Chapter 10, sections 10.1 and 10.2 and the lecture notes. Then complete these problems and turn in your completed homework during lecture

  1. (10 pts) Please fill in the information at the top of this homework sheet, as usual. WRITE DARK, and remember, if you MUST submit it on multiple sheets, JUST write your name at the top of both sheets and turn in both sheets UNCONNECTED. No staples, paper clips, fold/tear etc or anything that would jam up the scanner.

  2. (10 pts) What is the significance of a “base case” in a recursive function?

  3. On page 332, the author talks about two important properties of recursive functions:

    • There exist one or more base cases which provide the stopping condition for the functions
    • One or more recursive calls on arguments that are “closer” to the base cases (progress to the base case)

    For each of the following implementations of count(n), indicate which of the two properties are satisfied by circling the appropriate option. Then write the output when the function is called as count(4). If no output is produced, circle the “No output” option. If the execution never ends, circle “execution never ends” and write the first four characters printed. You may circle multiple options as appropriate. Finally write if either there is no output or execution never ends (or both), explain why that happened in light of the recursive properties that the function did not satisfy

    1. (10 pts) 
      def count(n):
  print(n)
  count(n-1)
      		Base case(s) exist Progress to base case
      No output produced Execution never ends Output:
    2. (10 pts) 
      def count(n):
  count(n-1)
  print(n)
      		Base case(s) exist Progress to base case
      No output Execution never ends Output:
    3. (10 pts) 
      def count(n):
  if n < 0:
    return
  count(n-1)
  print(n)
      		Base case exists Progress to base case
      No output Execution never ends Output:
    4. (20 pts) 
      def count(n):
  if n <= 0:
    print("Blast off!")
    return
  print(n)
  count(n)
      		Base case exists Progress to base case
      No output produced Execution never ends Output:
    5. (20 pts) </tr> 
      def count(n):
  if n <= 0:
    return 0
  result = n + count(n-1)
  print(result)
  return result
      		Base case exists Progress to base case
      No output Execution never ends Output:

  4. (10 pts) Consider the code in part(e) of the previous question. Show all the variables (and their values) in the program stack when the execution of the function reaches the base case, specifically right before the return statement in the if n<=0: clause is executed.