1RecursionLecture 4CS211 – Fall 2005Announcements• Assignment 2 is online (since Friday) Due date: Wednesday, September 14 Recommendation: Start now• If you would like a partner for A2 Sign up sheet Name and netID• Be sure to “form your group” on CMS! It does not happen automatically• For extra Java help Lots of consulting/office-hours are available• General Java-help is more easily available in week beforeassignment is due Can set up individual meetings with TAs via emailRecursion• Recursion is a powerful technique for specifying functions, sets, and programs• Recursively-defined functions and programs factorial combinations differentiation of polynomials• Recursively-defined sets grammars expressions data structures (lists, trees, ...)The Factorial Function (n!)• Define n! = n·(n−1)·(n−2)···3·2·1 read: “n factorial”• E.g., 3! = 3·2·1 = 6• By convention, 0! = 1• The function int → int that gives n! on input n is called the factorial function.• n! is the number of permutations of n distinct objects There is just one permutation of one object. 1! = 1 There are two permutations of two objects: 2! = 21 2 2 1 There are six permutations of three objects: 3! = 61 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1• If n > 0, n! = n·(n − 1)!Permutations ofPermutations of non-pink blocksEach permutation of the three non-pink blocks gives four permutations of the four blocks.Total number = 4·6 = 24 = 4!A Recursive Programstatic int fact(int n) {if (n = = 0) return 1;else return n*fact(n-1);}0! = 1n! = n·(n−1)!, n > 01126Execution of fact(4)fact(1)fact(4)fact(3)fact(0)fact(2)242General Approach to Writing Recursive Functions1. Try to find a parameter, say n, such that the solution for n can be obtained by combining solutions to the sameproblem with smaller values of n (e.g., chess-board tiling, factorial)2. Figure out the base case(s) — small values of n for which you can just write down the solution (e.g., 0! = 1)3. Verify that for any value of n of interest, applying the reduction of step 1 repeatedly will ultimately hit one of the base cases The Fibonacci Function• Mathematical definition:fib(0) = 0fib(1) = 1fib(n) = fib(n − 1) + fib(n − 2), n ≥ 2• Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, …two base cases!static int fib(int n) {if (n = = 0) return 0;else if (n = = 1) return 1;else return fib(n-1) + fib(n-2);} Fibonacci(Leonardo Pisano,1170−1240?)Statue in Pisa, ItalyGiovanni Paganucci,1863Recursive Executionstatic int fib(int n) {if (n == 0) return 0;else if (n == 1) return 1;else return fib(n-1) + fib(n-2);} fib(4)fib(3) fib(2)fib(1)fib(0)fib(2) fib(1)fib(1)fib(0)Execution of fib(4):= number of 2-element subsets of S = {A,B,C,D,E}• 2-element subsets containing A: {A,B}, {A,C}, {A,D},{A,E}• 2-element subsets not containing A: {B,C},{B,D},{B,E},{C,D},{C,E},{D,E}Therefore, = + Combinations (a.k.a. Binomial Coefficients)How many ways can you choose r items from a set S of n distinct elements? ()“n choose r”nr( )41( )42( )41( )42( )52()52Combinations• You can also show that = = + , n > r > 0= 1= 1( )nr( )n−1r( )n−1r−1( )nn( )n0( )nrn!r!(n−r)!3Combinations= + , n > r > 0= 1= 1( )nr( )n−1r( )n−1r−1( )nn( )n0( )00( )11( )10( )22( )21( )20( )33( )32( )31( )30( )44( )43( )42( )41( )4011 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1=Pascal’striangleThese are also called binomial coefficients because they appear as coefficients in the expansion of the binomial power (x + y)n:(x + y)n= xn+ xn−1y + xn−2y2+ ··· + yn= Σ xn−iyi( )ni( )nn( )n0( )n1( )n2ni = 0CombinationsCombinations have two base cases• Coming up with right base cases can be tricky!• General idea: Determine argument values for which recursive case does not apply Introduce a base case for each one of these• Rule of thumb: (not always valid) if you have r recursive calls on right hand side, you may need r base cases.Two base cases= + , n > r > 0= 1= 1( )nr( )n−1r( )n−1r−1( )nn( )n0Recursive Program for Combinationsstatic int combs(int n, int r){ //assume n>=r>=0if (r == 0 || r == n) return 1; //base caseselse return combs(n-1,r) + combs(n-1,r-1);}= + , n > r > 0= 1= 1( )nr( )n−1r( )n−1r−1( )nn( )n0Polynomial Differentiation Inductive cases:d(uv)/dx = u dv/dx + v du/dxd(u+v)/dx = du/dx + dv/dxBase cases:dx/dx = 1dc/dx = 0d(3x)/dx = 3dx/dx + x d(3)/dx = 3·1 + x·0 = 3Example:Positive Integer Powersan= a·a·a···a (n times)Alternative description:a0= 1an+1= a·anstatic int power(int a, int n) {if (n = = 0) return 1;else return a*power(a,n-1);}4A Smarter Version• Power computation: a0= 1 If n is nonzero and even, an= (an/2)2 If n is odd, an= a·(an/2)2• Java note: If x and y are integers, “x/y” returns the integer part of the quotient• Example: a5= a·(a5/2)2= a·(a2)2= a·((a2/2)2)2 = a·(a2)2Note: this requires 3 multiplications rather than 5!• What if n were higher? savings would be higher•This is much faster than the straightforward computation Straightforward computation: n multiplications Smarter computation: log(n) multiplicationsSmarter Version in Java• n = 0: a0= 1• n nonzero and even: an= (an/2)2• n odd: an= a·(an/2)2static int power(int a, int n) {if (n == 0) return 1;int halfPower = power(a,n/2);if (n%2 == 0) return halfPower*halfPower;return halfPower*halfPower*a;}Implementation of Recursive Methodsstatic int power(int a, int n) {if (n == 0) return 1;int halfPower = power(a,n/2);if (n%2 == 0) return halfPower*halfPower;return halfPower*halfPower*a;}• The method has two parameters and a local variable• Why aren’t these overwritten on recursive calls?parameterslocal variable• Key idea: Use a stack to remember parameters and local variables across recursive calls Each method invocation gets its own stack frame•A stack frame contains storage for Local variables of method Parameters of method Return info (return address and return value) Perhaps other bookkeeping infoImplementation of Recursive Methods• Like a stack of plates• You can push data on top or pop data off the top in a LIFO (last-in-first-out)
View Full Document
Unlocking...