CPSC 115L: Laboratory 4

CPSC 115L: Introduction to Computing

Fall 2010

Laboratory 5: Valued Functions and Recursion

October 6, 7

Preliminaries

Before coming to this lab, you should have read Chapter 6 of Downey, Fruitful Functions.

Objectives

The main objectives of this laboratory are

to learn how to design, implement and use valued functions in your programs,
to learn how to design, implement and use a recursive valued function.

Introduction

For this lab we will design and develop several functions. For each function, we will first develop an iterative solution (involving a loop) and then a recursive solution. For each function you should provide:

Preconditions: A brief description of the function's preconditions.
Postcondition: A brief description of the function's postcondition
Algorithm: An outline of the function's algorithm.

These may be written as comments in your python files and handed in with the function itself and its output. Here's an example for both the iterative and recursive versions of the factorial() function, which was covered in the text. Note that the functions have different names. Python does not let you overlaod function names. So you cannot have two different functions with the same name. (NOTE: Later we will learn how to use optional and default arguments to do pretty much the same thing.)

# Pre: n is a non-negative integer
# Post:  The factorial of n will be returned.
# Algorithm:  Accumulate the product of n * (n-1) * ... * 2 * 1

def factorial(n):
   ''' Computes n! for integer n >= 0 '''
   product = 1
   for i in range(1, n+1):
      product = product * i
   return product

# Pre: n is a non-negative integer
# Post:  The factorial of n will be returned.
# Algorithm:  Implements the following recursive definition:
#   0! = 1
#   n! = n * (n-1)!  for n > 0

def factorial_r(n):
    ''' Computes n! for integer n >= 0 '''
    if n == 0:
        return 1
    else:
        return n * factorial_r(n-1)

1. Numeric Functions

1.1. Write an iterative function named sum() that computes the sum of 1..n. This function should have a single integer parameter, n > 0.

1.2. Write a recursive function named sum_r() that computes the sum of 1..n for positive integer. This function should have a single integer parameter, n > 0.

1.3. Write an iterative function named sum_range() that computes the sum of m..n for positive integers, 0 ≤ m < n. This function should have two integer parameter.

1.4. Write a recursive function named sum_range_r() that computes the sum of m..n for positive integers, 0 ≤ m < n. This function should have two integer parameters.

1.5. Write an iterative function named power(x, n) that computes xⁿ for n ≥ 0. This function should have two parameters.

1.6. Write a recursive function named power_r(x, n) that computes xⁿ for n ≥ 0. This function should have two parameters.

2. Recursive Turtle Graphics

Both of the following figures were drawn recursively by repeatedly invoking a Turtle graphics square() function. From within the swampty folder, define a square() function that will draw a square for Turtle t with side of length l and then use that function to define recursive functions that draw one or both of the following shapes.

For instructions on how to start your Turtle graphics environment, see lab3.

Documentation

Each Python script should have a comment block at the beginning with your name, date, file name, and a brief description of the program, including the problem statement. Each function should be preceded by a comment block containing its pre- and post-conditions and an outline of its algorithm and each function should include a very brief docstring that describes the purpose of the function and its parameters.

What to hand in

Hand in one file containing both the iteretive and recursive version of each function.

CPSC 115L home page