Unformatted text preview:

Discrete Mathematics for ECE 14:332:202 Spring 2004 Recitation 7: Recursion Introduction: Recursive programming can greatly simplify a program, when the solution can be broken down into solutions of simpler problems. These programs make for very simplified code, but the same thing can usually programmed iteratively (while/for loops) in a much more straightforward manner. Take the classic example of computing n!, factorial(n). This can be expressed mathematically as: )!1(*2...)2()1(!122−=⋅==⋅⋅−⋅−⋅=∏∏−==nnknknnnnnknk Taking n out of the product, the operation can be expressed as n*factorial(n-1), which will iteratively call the function to a computation of one less than before. This could be coded in MATLAB very simply: function f = factorial(n) if (n < 2) f = 1; else r = n*factorial(n-1); end Trace yourself through this algorithm for n = 7, and you’ll get a good feel for how a simple recursive program operates. Now, let’s turn to the example of the Euclidian algorithm, and determine how this could be programmed recursively – calling the same function with simpler arguments each time, until the base case is reached. Let’s begin with a familiar numerical example: d = gcd(a,b) = gcd(1180,482). a = q*b + r 1180 = 2*482 + 216 482 = 2*216 + 50 216 = 4* 50 + 16 50 = 3* 16 + 2 16 = 8* 2 + 0 From the calculation, we see that d = 2, but we came across several simpler computations that arrived at the same answer, gcd(482,216) = 2, gcd(216,50) = 2, gcd(50,16) = 2, etc. We have seen how to program this iteratively, which follows the calculation, but to program it recursively is a little more involved. We want each step of the recursion to break the problem down into a simpler one, such as a and b getting smaller until the gcd calculation is trivial (such that our recursion stops – the base case, when r = 0). Here is our method: until r = 0 is reached: Calculate r and q, so that you have your new a and b Recursively call gcd on your new a when r = 0 is reached: return d = b.Here is how the code would look (assuming a > b): function d = rx_gcd(a,b) q = floor(a/b); r = a -q*b; if r == 0 d = b; else a = b; b = r; d = rx_gcd(a,b); end You always have to make sure in recursive programming that your recursive calls return some value (in MATLAB this is done by assigning the output to a variable). Exercises: 1. Read the notes and examine the function rx_euclid.m. Modify the function to display the steps of the operation (good enough so all the calculations are clearly seen). See that it performs the same calculation as the iterative version. 2. Consider the Tower of Hanoi game as described on p.131 of the text. Implement the pseudo-code given in MATLAB as a recursive function toh_moves.m, that prints the required moves to solve the puzzle to the screen. (use disp(sprintf(‘ ‘, , )) ). Verify that it works by using a quarter, dime, nickel and penny for the disks, n = 4. Make the moves as instructed and observe how the problem has been broken up into successively smaller problems. Additional Exercises: 1. Write a recursive guessing game program: The user picks a secret number between 1 and 100 and your program does the guessing. After each guess, the user responds with “too high”, “too low”, or “correct”. Your main program should simply be one call to your recursive procedure or function. (Problem 5, p. 137) Extra Credit: Now, let’s take the Tower of Hanoi game one step further by keeping track of the positions of the disks in 3 vectors, contained in a cell array, pegs, so that the actual movement of the disks can be shown. This may be a rather difficult task, but give it a good shot, and if you’re lucky, I may mass-email hints. One possibility: Save your instruction set in some matrix, then iteratively follow the instruction set to perform the operations on the cell array containing your disk information. If you’re really brave: Use the cell array pegs as the output of the function toh, so that it is modified each time an instruction is given (recursively change pegs). What your cell array would look like for n = 5: >> pegs{1} ans = 5 4 3 2 1 >> pegs{2} ans = [] >> pegs{3} ans = []


View Full Document

Rutgers University ECE 202 - Recitation 7- Recursion

Download Recitation 7- Recursion
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Recitation 7- Recursion and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Recitation 7- Recursion 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?