CSC111 Lab 13

--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
    y = fact( n-1 )
    result = n * y
    return result


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

main()

Run your program and verify that it computes the correct result. Below are some factorials numbers to compare your output to.

  1! =                    1
  2! =                    2
  3! =                    6
  4! =                   24
  5! =                  120
  6! =                  720
  7! =                 5040
  8! =                40320
  9! =               362880
 10! =              3628800
 11! =             39916800
 12! =            479001600
 13! =           6227020800
 14! =          87178291200

Question 1

• Add print statements to your fact function so that it will print exactly what it does. For example, before it tests to see if n is less than equal to 1, you could print:

    print "fact function started.  Receives n =", n
    print "testing if n is >= 1"

• Add print statements that will show the values of y and result.

• Run your program and observe the print statements. Can you see better how fact recursively calls itself?

Question 2

• Create the more sophisticated program shown below. Observe it well and try to figure out what the indent variable does.

# factorialPrint.py
# Demonstrates a recursive factorial function
 
def fact( n, indent ):
    print indent, "fact(%d) started" % n
    print indent, "comparing %d to 1" % n
    if n<=1: 
        print indent, "%d is <= 1.  Returning 1" % 1
        return 1

    print indent, "%d is not <= 1.  Calling fact(%d) and storing it in y" % (n, n-1)
    y = fact( n-1, indent + "    "  )
    print indent, "just received %d from fact( %d )." % ( y, n-1 )
    result = n * y
    print indent, "multiplied %d by %d.  It's %d.  Returning %d to caller" % ( n, y, result, result )
    return result
 
 
def main():
    # print first 15 factorials 
    n = input( "Enter a positive integer: " )
    print "Main calls fact( %d )" % n 
    y = fact( n, "   " )
    print "Main receives result = ", y
 
main()

• Run the program
• Explain the pattern made by the printed lines. Why this shape?
• Where does the stopping condition appear in the printed lines?

Exercise: Write a recursive function

• Write a program with a recursive function. The function returns the largest element of a list using the following formula:

   largest( A )  = A[0]                                   if len( A ) == 1
   
                 = max( A[0], largest( A[1:] ) )          otherwise

• Test your program on different Arrays of varying sizes. We assume that the arrays will always have at least one element.

def largest( A ):
   if len( A )==1:
      return A[0]
   return max( A[0], largest( A[1:] ) )

Exercise: A more sophisticated recursive function

• This time the largest is defined as the max of the largest of the left half of the array, and of the largest of the right half of the array.

   largest( A )  = A[0]                                                   if len( A ) == 1
   
                 = max( largest( A[0:N/2], largest( A[N/2:] ) )          otherwise.  N=len(A)

Binary Search

• Create a copy of the binary search program we saw in class yesterday.
• 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, we'll call it 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.

# program header
# 
count = 0
 
def binsearch( ... ):
    global count

    ...
    count += 1


def main():
    global count
    
    ...
    count = 0
    binarySearch( ... )
    ...

• 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!

Second question

• How does the number of probes it takes to find an item relate to the size of the array you are searching.
• To answer this question, modify your program so that you can set the size of the array before you start searching it. Record the number of probes (the average is fine), for lists of size 20, 1000, 10,000, or 100,000.

Exploring a Maze

• Get a copy of the maze-visiting program, and run it.

• Observe how the recursive visitMaze() function leaves "bread crumbs" behind the cells that it visits, and "v" characters in cells visited but known not to lead to an exit.

• Edit the program and switch the order in which it visits cells in the 4 directions. Make the recursive function decide to go up first, then left, then right, and finally down.

• Run the program and see how this change influences the path found.

• Modify your program so that the maze is now a much simpler maze, in the spirit of the maze shown below:

     mazeText = """
     #########################
     ........................#
     #.......................#
     #.......................#
     #...........#...........#
     #...........#...........#
     #############...........#
     #...........#...........#
     #.......................#
     #........################
     #........................
     #.......................#
     #.......................#
     #########################
     """

• Predict the path that the program is going to take when visiting it.

• Repeat the same experiment as before and change the order in which the recursive function visits the different directions, and observe if this makes the function find the exit faster.

Treasure in the maze

• Let's change the rules of the game, and make your program find a path to a treasure, rather than a path to an exit. In our case the treasure will be a special character, say '&', inside the maze.

• Modify your the visitMaze() function so that it now returns true if it finds the treasure, and not an exit. Verify that your program displays at the end the path to the treasure.