Lecture Notes
Introduction to Programming and Algorithm Design
(COP1000)
Fruitful functions
This chapter shows how to write fruitful functions – those
that return values to the function that called them.
Return values
 If a function is written so that it returns a value, we call
it a fruitful function
 A fruitful function can be used in an expression; the value
returned by the function "takes the place" of the function call:
>>> print round(89.6) + 4
94.0
 We write fruitful function definitions by using the
return keyword followed by an
expression:
return expression
Incremental development
 The key to writing larger and more complex programs is incremental development
 The idea is to design and code in logical "chunks" that
include only a few new lines of code that we can then easily
test
 The example in this section shows how to develop a
moderately complex function (compute the distance between two
points on the Cartesian plane) incrementally – one step at a time:
>>> def distance(x1, y1, x2, y2):
# 1st try
return 0.0
>>> distance(1, 3, 6, 4)
# 1st test
0.0
>>> def distance(x1, y1, x2, y2): # 2nd
try
dx = x2  x1
dy = y2  y1
print "dx =", dx
print "dy =", dy
return 0.0
>>> distance(1, 3, 6, 4)
# 2nd test
dx = 5
dy = 1
0.0
>>> def distance(x1, y1, x2, y2): # 3rd
try
dx = x2  x1
dy = y2  y1
dsquared = dx**2 + dy**2
print "dsquared =", dsquared
return 0.0
>>> distance(1, 3, 6, 4)
# 3rd test
dsquared = 26
0.0
>>> def distance(x1, y1, x2, y2): # 4th
try
dx = x2  x1
dy = y2  y1
dsquared = dx**2 + dy**2
result = math.sqrt(dsquared)
return result
>>> distance(1, 3, 6, 4)
# 4th test
5.0990195135927845
 Key aspects of the incremental design process:

Start with a working program and
make small, incremental changes
 Use temporary variables to hold intermediate results so you
can output and check them

Once the program is working, you
can go back and remove or consolidate some of the "scaffolding"
or multiple statements into compound expressions, but don't
sacrifice readability for compactness!
 An important observation by
Donald Knuth:
Premature optimization is the root of all evil.
Composition
 The ability to call one function from within another is
called composition
 Here is a program (intercept.py)
that calculates the yintercept of a line given the coordinates
of two points on the line, using composition, as suggested by
the exercise on page 52
Boolean functions
 A boolean function is one that returns only a 1
(true) or 0 (false)
 A boolean function is often used implement a test; its
return value can then be used as a condition in an
if statement
 For example, here is a function that returns true (1) if the
first argument is evenly divisible by the second of false (0)
otherwise:
>>> def is_divisible(x, y):
if x % y == 0:
return True
else:
return False
>>> is_divisible(19, 6)
False
>>> is_divisible(18, 6)
True
 Notice that the condition x % y == 0
itself evaluates to True or
False, so we can simplify the above
function to:
>>> def isDivisible(x, y):
return (x % y == 0)
>>> isDivisible(100,10)
True
 Now we can use the function anywhere we could use a
condition:
>>>if isDivisible(81, 9):
print "Divisible!"
else:
print "Not divisible!"
Divisible!
 See the example program
islower.py for another
example of a Boolean function
More recursion
 This section explains that we have already covered all the
techniques needed to write any program that can be written
 The proof of this fact was first demonstrated by
Alan Turing (for
whom the ACM's
Turing Award – the "Nobel Prize of Computer Science" is
named; see also more information on
Turing
Machines and the
Turing Test)
 Also described is the recursive logic to compute the
factorial of an integer, n!, which is defined as:
0! = 1
n! = n(n  1)!
Leap of faith
 Recursion does require a "leap of faith," in that you can
trace the logic through for very many recursions – it's just to
cumbersome
 Instead, ask if the base case works, and, if it does, if you
have covered all other possibilities
One more example
 This section describes another deeply studied sequence, the
Fibonacci sequence, defined as:
fib(0) = 1
fib(1) = 1
fib(n) = fib(n  1)
+ fib(n  2)
(for n > 1)
 That is, each Fibonacci number is the sum of the previous
two Fibonacci numbers; here is the beginning of the sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
 See the example program
fibonacci.py that
generates the Fibonacci sequence, using recursion
 Note: the example program, while accurate, is not very
efficient; using it, calculating fibonacci(200) would
require 2^{92} seconds on the world's fastest computer;
there are more efficient algorithms, but none as compact as the
one given
 See also a
Fibonacci animation, and
Fibonacci in nature web pages
Checking types
 If our logic depends on the user providing a value of a
specific type (int or
float), we can check this with the
type() function:
>>> print type(1)
<type 'int'>
>>> x = input("Enter a number: ")
Enter a number: 12.7
>>> if type(x) == type(1):
print "You entered an integer!"
else:
print "You entered a floating point!"
You entered a floating point!
