CSC111 Lab 13

From dftwiki3
Revision as of 10:09, 28 April 2010 by Thiebaut (talk | contribs) (Created page with '--~~~~ ---- {| | __TOC__ | <bluebox> This lab deals with recursive functions. </bluebox> |} ==Factorial== Create a copy of this simple example: <source lang="python"> # facto…')
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

--D. Thiebaut 15:09, 28 April 2010 (UTC)


This lab deals with recursive functions.

Factorial

Create a copy of this simple example:

# factorial.py
# Demonstrates a recursive factorial function

def fact( n ):
    if n<=1: 
        return 1
    return n * fact( n-1 )


def main():
    n = input( "Enter a positive number: " )
    x = fact( n )
    print "the factorial of %d is %d." % ( n , x )

main()

Binary Search

Create a copy of the binary search program we saw recently in class. Observe the main function. Make sure you figure out how large the array is.

Run the program and verify that the search function does a good job locating or not the numbers.

First problem

Modify the program so that it counts the number of comparisons that it performs. A good way to do this is to create a global variable, count that is declared at the beginning of your program, and which you increment by one, every time the binsearch function compares two quantities. These comparisons are a good indicator of the amount of "work" done by the function, since it is obvious just looking at the program to figure out how much time the function will call itself. The correct way to use count as a global variables is illustrated below. You initialize the variable at the beginning of the program, and in the functions that need to use it, you define count as global so that python will know that count is not just a local variable used inside the function, but refers to something defined outside the function.

  1. program header

count = 0

def binsearch( ... ):

   global count
   ...
   count += 1


def main():

   global count
   
   ...
   count = 0
   binsearch( ... )
   ...

Make the main program print the number of comparisons performed after the function returns to main.

Make sure you reset the counter to 0 for every new search!