TAILIEUCHUNG - Lecture Data structures and algorithms in Java (6th edition): Chapter 5 - Goodrich, Tamassia, Goldwasser

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 -

• Cơ sở dữ liệu
• Data structures
• Data structures and algorithms
• Computer science
• Design of data structures
• Algorithms in Java
• Analyzing recursive algorithms
• Ebook Data structures and algorithms made easy
• Data structures and algorithms made easy
• Data structures and algorithmic puzzles
• Data structures for storing strings
• Algorithms design techniques
• algorithms
• data structure lectures
• structured document data
• teaching data structures
• algorithms in data structures
• Lecture Data Structures
• Bài giảng Cấu trúc dữ liệu
• Programming assignments
• Data structures organize data
• Resource constraints
• Lecture Data structures and algorithms
• Cấu trúc dữ liệu và giải thuật
• Abstract data type
• Lecture ECE 250
• Lecture Algorithms and data structures
• Algorithm analysis
• Graph algorithms
• Memory allocation
• AVL trees
• Binary search trees
• Red black trees
• Splay trees
• Dynamic programming