Lecture Notes
Introduction to Programming and Algorithm Design (COP-1000)

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:
    1. Start with a working program and make small, incremental changes

    2. Use temporary variables to hold intermediate results so you can output and check them
    3. 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 y-intercept 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 292 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!

 Updated: 12.13.2010