1
h13
CCS CS20 S18
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 (Introduction to Recursion - up to Practice Problem 10.3)

ready? assigned due points
true Thu 05/24 12:30PM Thu 05/31 12:30PM

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

This assignment should be submitted by scanning the pages in the correct order to a PDF file and uploading to gradescope.com.

For more information, visit ucsb-cs8.github.io and look for Gradescope: Student Self Submission under "topics".

Even though it is a Gradescope submission, nevertheless, *please fill in the information at the top of this homework sheet*, including your name and umail address.

READING ASSIGNMENT

Please read Perkovic 10.1 (Introduction to Recursion - up to Practice Problem 10.3). Then complete these problems and turn in your completed homework in lecture on the due date.

  1. (10 pts) These 10 points are for filling in your name at the top of the sheet, and scanning correctly on Gradescope. (Having these here gives me a place to give you feedback if there is some glitch with the way you are doing it.)

  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 checking the appropriate boxes. You might check only one of the two boxes, both boxes, or neither.

    Then determine what the output will be (if any) when the function is called as count(4). If no output is produced, check the “No output” option. If the execution never ends, check the “execution never ends” and write only the first three lines of output.

    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 produced ☐ Execution never ends
      Output:
    3. (20 pts) 
      def count(n):
  if n < 0:
    return
  count(n-1)
  print(n)
      		☐ Base case(s) exist ☐ Progress to base case
      ☐ No output produced ☐ Execution never ends
      Output:
    4. (20 pts) 
      def count(n):
  if n <= 0:
    print("Blast off!")
    return
  print(n)
  count(n)
      		☐ Base case(s) exist ☐ Progress to base case
      ☐ No output produced ☐ Execution never ends
      Output:
    5. (20 pts) 
      def count(n):
  if n <= 0:
    return 0
  result = n + count(n-1)
  print(result)
  return result
      		☐ Base case(s) exist ☐ Progress to base case
      ☐ No output produced ☐ Execution never ends
      Output: