tailieunhanh - Lecture Java methods: Object-oriented programming and data structures (3rd AP edition): Chapter 13 - Maria Litvin, Gary Litvin

Chapter 13 - . In this chapter, the learning objectives are: Learn about interface; learn about the class, its constructors and methods; review some of the ArrayList pitfalls; practice with Part 4 of GridWorld ― “Critters”. | Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition Chapter(13) = Chapter(12) + 1 Algorithms and Recursion 13- In Chapter 7 we introduced algorithms with iterations. In this chapter we consider recursive methods. Objectives: Learn about recursion Learn to interpret and write recursive methods 13- Recursion is another tool for describing algorithms and implementing them in computer programs. Properties of Algorithms Compactness: an algorithm can use iterations or recursion to repeat the same steps multiple times Generality: the same algorithm applies to any “size” of task or any input values Abstractness: an algorithm does not depend on a particular computer language or platform (although it may depend on the general computing model) 13- Iterations and recursion make an algorithm different from a cookbook recipe. In most cookbook . | Copyright © 2015 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved. Java Methods Object-Oriented Programming and Data Structures Maria Litvin ● Gary Litvin 3rd AP edition Chapter(13) = Chapter(12) + 1 Algorithms and Recursion 13- In Chapter 7 we introduced algorithms with iterations. In this chapter we consider recursive methods. Objectives: Learn about recursion Learn to interpret and write recursive methods 13- Recursion is another tool for describing algorithms and implementing them in computer programs. Properties of Algorithms Compactness: an algorithm can use iterations or recursion to repeat the same steps multiple times Generality: the same algorithm applies to any “size” of task or any input values Abstractness: an algorithm does not depend on a particular computer language or platform (although it may depend on the general computing model) 13- Iterations and recursion make an algorithm different from a cookbook recipe. In most cookbook instructions, each step is performed once. This works because the chef is slow. But a computer is very fast, billions of times faster than a programmer. If we had to write out separately every instruction that a computer executes, we wouldn’t be able to take advantage of its speed. In non-trivial algorithms, the same sequences of steps are repeated multiple times (but the values of variables are updated at each step). Recursion A recursive solution describes a procedure for a particular task in terms of applying the same procedure to a similar but smaller task. Must have a base case when the task is so simple that no recursion is needed. Recursive calls must eventually converge to a base case. 13- Students who are interested in algorithms may be intrigued by recursion and may try to come up with recursive versions of common algorithms. Others never quite “get it.” Recursion: an Example Procedure: Climb steps Base case: if no steps to climb stop Recursive case: more steps to climb