CSC111 Lab 13 2015b
--D. Thiebaut (talk) 20:44, 6 December 2015 (EST)
This lab deals with recursive functions. Programming recursive functions is a challenging concept to master. The best way to proceed is to write many different recursive solutions and observe the behavior of the functions as they perform their work. Eventually recursion will start making sense. It is normal not to fully understand recursion at first. Keep at it. Little by little, it will become natural thinking.
|
Visualizing Recursive Factorial At Work
Create a copy of this simple example:
# factorial.py # Demonstrates a recursive factorial function def fact( n ): # stopping condition if n<=1: return 1 # recursive step y = fact( n-1 ) result = n * y return result def main(): n = int( input( "Enter a positive number: " ) ) x = fact( n ) print( "{0:3}! = {1:20}".format( 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 is a table of factorial numbers to verify that your program outputs the correct information. Note that your program must output only one line, with n and n! on it.
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", n, "is >= 1" )
- 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, "1 is <= 1. Returning 1" ) return 1 print( indent, n, "is not <= 1. Calling fact2(",n-1,") and storing it in y" ) y = fact2( n-1, indent + " " ) print( indent, "just received", y, "from fact2(",n-1,")." ) result = n * y print( indent, "multiplied", n,"by", y, " = ", result, "Returning", result, "to caller" ) return result def main(): n = int( input( "Enter a positive integer: " ) ) print( "Main calls fact(",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?
Thinking Recursively
All the challenges below require you to put together a recursive function for a simple problem.
Thinking recursively is quite challenging and takes a while to master. So don't despair!
Here are points to remember when building a recursive function:
- First, figure out what the function will return to the main program. Will it return a boolean? An integer? A list? Then when the function calls itself recursively, that's what it should expect to receive back from a call to itself.
- What is the stopping condition? What is the smallest problem you can solve without recursion? That's the first thing you want to test for and do in your recursive function.
- If the stopping condition doesn't apply, and the function has to do some work, figure out how to make one or several recursive calls to the function, get some intermediate results back, combine them together and get the final answer. That's the recursive step.
- First, figure out what the function will return to the main program. Will it return a boolean? An integer? A list? Then when the function calls itself recursively, that's what it should expect to receive back from a call to itself.
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 15 (which is equal to 5+4+3+2+1)
Challenge 2: Recursive Even Sum |
- Given a number n, compute recursively the sum of all the positive even 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
Recognizing Palindromes
A palindrome is a sentence that can be read forward and backward. For example "Able was I ere I saw Elba." Another one: "A man, a plan, a canal: Panama."
For this lab you are asked to write a function that is given a list, and that returns True if the list is a "palindromic", that is, if the list of items is the same scanning forward and scanning backward. Below are example of lists that are "palindromic":
- [ 1, 10, 1 ]
- [ "hello", "hello" ]
- [ 1, "hello", "hello", 1 ]
- [ 1, 2, 10, -1, 10, 2, 1 ]
First, with your partner, generate a some lists that are not palindromes, and see what makes them so, compared to the lists above.
Explore several ways our collection of minions would do the work, if asked to figure out if a list was palindromic or not. You would give the whole list to a minion, who would be doing a tiny bit of work, then reduce the list, and possibly pass it on to another minion, who would do the same amount of work, etc, until one minion gets a list that is small enough that it can decided if it is a palindrome or not.
Write a program called lab13_1.py that contains a main program that takes different lists and tests wether they are palindromic using your recursive function. Here's a possible main() function for your program:
def main(): # prompt user 10 times for i in range( 10 ): # get a List from the user (must contain [ and ]) L = eval( input( "Enter a list: " ) ) print( "L = ", L ) # test if palindrome or not if isPalindrome( L ): print( "is a palindrome" ) else: print( "is NOT a palindrome" ) main()
- Note
- Any list with only 1 element in it is a palindrome. We will assume that the empty list [] is a palindrome.
Fractal Trees
- This exercise is for you to explore recursion in a graphic context.
- Create a new program with the code you'll find on this page, put it in the same directory where you store your graphics.py directory. You may want to call your program lab13_3.py.
- The program will generate a fractal tree. Fractals are self-similar objects: they look the same on a small scale as they do on a larger scale.
- Run the program first.
- Look at the code and see if you can figure out how the recursion works.
- To see how the different parameters influence the drawing of the fractal tree, modify the following parameters, one at a time, and give them different values:
- theta
- in the main program, change the angle theta which controls how much a branch will diverge from the direction of the branch that supports it. Try 0.4 first. Then try values between 0 and 0.8.
- level of recursion
- the main program passes 9 to the function as a starting level of recursion. Try passing smaller numbers first, then larger numbers (but less than 13 or so).
- trunk_ratio
- Originally set to 0.29, it represents the length of the trunk relative to its two branches. Try ratios between 0.1 (10%) and 0.9 (90%).
Play!
- Here are some ideas for modifications you may bring to the program:
- draw the left branches red, and the right branches yellow
- make the size of the branch shrink as the function draws smaller and smaller branches (the trunk will be the fattest branch). Note: the graphic objects in the graphics.py library have a setWidth(pixels) method to define the width of the lines.
- Draw green circles at the end of the very last branches (when the recursion ends) to simulate leaves in the tree.
Moodle Submission
- Submit your program for the recursive even sum problem.
- Call your program lab13.py
- Call your recursive function evenSum()
- Make your main() function prompt the user for an integer and display the sum of all even numbers less than or equal to that integer. You may assume that the user will always enter a valid integer. Here is what your main function should look like:
def main(): n = int( input( "> " ) ) print( "-*-" ) # <-- make sure your program prints this to separate input from output! print( sumEven( n ) ) main()
- Submit your program in the Moodle Lab 13 section.
<showafterdate after="20151212 00:00" before="20151231 00:00">
Solution Programs
Even Sum
# recursiveEvenSum.py def sumEven( n ): if n <= 1: return 0 if n % 2 == 1: return sumEven( n-1 ) return n + sumEven( n-2 ) def main(): for n in range( 0, 12 ): print( "n = {0:1} sumEven({1:1}) = {2:1}" .format( n, n, sumEven( n ) ) ) main()
Other Programs
# solution programs for Lab13 2015 # # from random import randrange def fact( n ): print( "fact function started. Received n =", n ) print( "testing if %d is >= 1" % (n) ) if n<=1: print( "n == 1. Returning 1" ) return 1 print( "n > 1. Calling fact( %d )" % (n-1) ) y = fact( n-1 ) print( "setting y to %d" % y ) result = n * y print( "returning result = %d * %d = %d" % (n, y, n*y) ) return result 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 sum1( n ): if n==1: return 1 return n + sum1( n-1 ) def evenSum1( n ): if n <= 1: return 0 if n%2 == 0: return n + evenSum1( n-2 ) if n%2 == 1: return evenSum1( n-1 ) def main(): # fact """ n = int( input( "Enter a positive number: " ) ) x = fact( n ) print( "the factorial of %d is %d." % ( n , x ) ) """ # fact2 """ n = int( input( "Enter a positive number: " ) ) x = fact2( n, " " ) print( "the factorial of %d is %d." % ( n , x ) ) """ # sum1 """ n = int( input( "Enter a positive number: " ) ) print( "sum of all numbers from 1 to %d = %d" % (n, sum1(n) ) ) """ # evenSum1 """ for n in range( 12 ): print( " n = %d sumEven(%d) returns %d" % (n, n, evenSum1(n) ) ) """ main()
Palindrome
# Problem for Lab 12 # def display( List ): for item in List: # is item an integer? if type( item )==type( 3 ): # yes, then print it print( item, " ", end="", sep="" ) else: # no, it's a list, call display # recursively on this list. display( item ) def isPalindrome( L ): # stopping conditions: # a list of 1 is a palindrome if len( L )<=1: return True # a list of 2 identical items is a palindrome if len( L )==2 and L[0]==L[1]: return True # if first is not equal to last, not a palindrome # for sure! if L[0] != L[-1]: return False # otherwise, the first and last should be the same, # since we're here. Figure out if what is in-between # is a palindrome. return isPalindrome( L[1:-1] ) def main(): while True: L = eval( input( "Enter a list: " ) ) #[ 1, 2, [3, 4], 5, [6, 7], [8,[9,10] ] ] print( "L = ", L ) if isPalindrome( L ): print( "is a palindrome" ) else: print( "is NOT a palindrome" ) main()
</showafterdate>