CSC111 Lab 13 2014

--D. Thiebaut (talk) 19:43, 28 April 2014 (EDT)

---

This lab deals with recursive functions, and solving problems recursively.

Program Name

• Call your program lab13.py

Visualizing Recursive Factorial At Work

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 = int( input( "Enter a positive number: " ) )
    x = fact( n )
    print( "the factorial of %d is %d." % ( n , x ) )

main()

• Run your program
• It will prompt you for a number and will return its factorial.
• 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

Visualizing, Step 1

• Add print statements to your fact() function so that it will let you know 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 %d is >= 1" % (n) )

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

• Run your program and observe its output. Can you see better how the function fact() recursively calls itself?

Visualizing, Step 2

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

# factorialPrint.py
# Demonstrates a recursive factorial function
 
def fact2( n, indent ):
    print( indent, "fact2(%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 fact2(%d) and storing it in y" % (n, n-1) )
    y = fact2( n-1, indent + "    "  )
    print( indent, "just received %d from fact2( %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():
    n = input( "Enter a positive integer: " )
    print( "Main calls fact( %d )" % n  )
    y = fact2( 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? In other words, where is the printed statement that indicates that fact() just received a value of n equal to 1? Why isn't this statement at the end of the printout?

Challenge 1: Recursive Sum

• Given a number n, compute recursively the sum of all the numbers from 1 to n. For example, if you pass n = 5 to the solution function, it will return 5+4+3+2+1 = 15

Challenge 2: Recursive Even Sum

• Given a number n, compute recursively the sum of all the even and positive numbers less than or equal to n.
• This is trickier than it seems! Here is an example of running a loop and asking the recursive function to compute the sum of all the even numbers up to n when n ranges from 0 to 12.

n = 0  sumEven(0) returns 0
n = 1  sumEven(1) returns 0
n = 2  sumEven(2) returns 2
n = 3  sumEven(3) returns 2
n = 4  sumEven(4) returns 6
n = 5  sumEven(5) returns 6
n = 6  sumEven(6) returns 12
n = 7  sumEven(7) returns 12
n = 8  sumEven(8) returns 20
n = 9  sumEven(9) returns 20
n = 10  sumEven(10) returns 30
n = 11  sumEven(11) returns 30

Challenge 3: Recursive Max

• Write a recursive function that returns the largest element of a list L using the following formula:

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

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

Hints

• the function definition is simply def largest( L ):
• write the stopping condition first (if len(L)...)
• if the stopping condition is not met, compute the max() of L[0] and largest( L minus the first element )

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

Divide and Conquer Recursion

• We now take a slightly different approach. This time we take a list, divide it two halves, recursively process the two halves, and combine the result of the results obtained on both sides.

• As an example, assume we have to find the largest item in a list L. Here's a possible way to describe the recursive divide-and-conquer approach:

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

The code equivalent to this definition is shown below:

def divideConquerLargest( L ):
     N = len( L )
     if N==1:
           return L[0]

     return max( divideConquerLargest( L[0:N//2] ),
                divideConquerLargest( L[N//2: ] ) )

• Run this code, and verify that it returns the largest element of an unsorted list of integers.

    L = [1, 2, 3, 0, 10, 20, 30, 3, -3, 5, 1, 100, 1]
    print( "divideConquerLargest( %s ) = %d" % (L, divideConquerLargest(L ) ) )

Challenge 4: Divide-and-Conquer Min

• Write a recursive function that uses the divide and conquer approach to find the smallest element in a list L.

Challenge 5: Divide-and-Conquer Sum

• Write a recursive function that uses the divide and conquer approach to compute the sum of all the elements in a list L.

Challenge 6: Divide-and-Conquer Absolute Value

• Write a recursive function that uses the divide and conquer approach to change all the numbers in a list L to their absolute value.

(Hints: the code is much simpler than you think!)

Binary Search

• Create a copy of the binary search program we saw in class.
• Read the whole program. Figure out what is going on.
• Run the program and verify that the search function does a good job reporting whether a key entered by the user is in the list or not.

First Modification

• Modify the recursive function and make it print its parameters (with the exception of A which will be printed in main and does not change).
• Run the program.
• Observe how the binary function quickly reduces the search domain to zoom in the place where the key should be located, if it is in the list.

Second question

• Keep the modification you performed in the previous step.
• Modify the main program as follows

    A = createArray( 10000 )
    print( A[100:110] )

This way you will have a large array and your program will show a small section of 10 consecutive numbers stored in it.

• Run your program and pick keys that are either listed in the array of 10 consecutive array items, or pick keys that are in between some of the 10 numbers (i.e. not in the list). Observe how few steps are required to see if the keys are in the list or not.
• Make your List of size 1,000,000. Predict how many recursive steps are required to find whether a kew is in the list or not. Verify if your intuition is correct or not. Note: your program will spend a few seconds at the beginning creating and sorting the array. Be patient!
• Is the number of steps required to find a number always the same? Could it be possible to find a number in the list with just one probe? See if you can make it happen and demonstrate your solution to me!

Submission

Submit the program hw13.py to this URL: http://cs.smith.edu/~thiebaut/111b/submitL13.php