One way to describe repetition within a computer program is the use of loops, such as Java’s while-loop and for-loop constructs described in previous chapter. An entirely different way to achieve repetition is through a process known as recursion. | Recursion 3/16/14 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Recursion © 2014 Goodrich, Tamassia, Goldwasser Recursion 1 The Recursion Pattern q q q q Recursion: when a method calls itself Classic example – the factorial function: n! = 1· 2· 3· ··· · (n-1)· n Recursive definition: 1 if n = 0 ⎧ f (n) = ⎨ else ⎩ n ⋅ f (n − 1) As a Java method: © 2014 Goodrich, Tamassia, Goldwasser Recursion 2 1 Recursion 3/16/14 Content of a Recursive Method q Base case(s) n n q Values of the input variables for which we perform no recursive calls are called base cases (there should be at least one base case). Every possible chain of recursive calls must eventually reach a base case. Recursive calls n n Calls to the current method. Each recursive call should be defined so that it makes progress towards a base case. © 2014 Goodrich, Tamassia, Goldwasser Recursion 3 Visualizing Recursion q Recursion trace n n n q Example A box for each return 4 * 6 = 24 final answer call recursive call recursiveFactorial ( 4 ) An arrow from each call return 3 *2 = 6 caller to callee recursiveFactorial ( 3 ) call return 2 *1 = 2 An arrow from each recursiveFactorial ( 2 ) callee to caller call return 1 *1 = 1 showing return value recursiveFactorial ( 1 ) call return 1 recursiveFactorial ( 0 ) Recursion © 2014 Goodrich, Tamassia, Goldwasser 4 2 Recursion 3/16/14 Example: English Ruler q Print the ticks and numbers like an English ruler: Recursion © 2014 Goodrich, Tamassia, Goldwasser Using Recursion 5 Slide by Matt Stallmann included with permission. drawInterval(length) Input: length of a ‘tick’ Output: ruler with tick of the given length in the middle and smaller rulers on either side drawInterval(length) if( length > 0 ) then drawInterval ( length - 1 ) draw line of the given length drawInterval ( length -
