Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Object Oriented Programing - Chapter 15: Recursion

In this chapter you will learn: The concept of recursion, how to write and use recursive methods, how to determine the base case and recursion step in a recursive algorithm, how recursive method calls are handled by the system, what geometric shapes called fractals are and how to draw them using recursion. | 15 Recursion We must learn to explore all the options and possibilities that confront us in a complex and rapidly changing world. —James William Fulbright O! thou hast damnable iteration, and art indeed able to corrupt a saint. —William Shakespeare Its a poor sort of memory that only works backwards. —Lewis Carroll, Alice in Wonderland Life can only be understood backwards; but it must be lived forwards. —Soren Kierkegaard Push on—keep moving. —Thomas Morton OBJECTIVES In this chapter you will learn: The concept of recursion. How to write and use recursive methods. How to determine the base case and recursion step in a recursive algorithm. How recursive method calls are handled by the system. The differences between recursion and iteration, and when it is appropriate to use each. What geometric shapes called fractals are and how to draw them using recursion. What recursive backtracking is and why it is an effective problem-solving technique. 15.1 Introduction 15.2 . | 15 Recursion We must learn to explore all the options and possibilities that confront us in a complex and rapidly changing world. —James William Fulbright O! thou hast damnable iteration, and art indeed able to corrupt a saint. —William Shakespeare Its a poor sort of memory that only works backwards. —Lewis Carroll, Alice in Wonderland Life can only be understood backwards; but it must be lived forwards. —Soren Kierkegaard Push on—keep moving. —Thomas Morton OBJECTIVES In this chapter you will learn: The concept of recursion. How to write and use recursive methods. How to determine the base case and recursion step in a recursive algorithm. How recursive method calls are handled by the system. The differences between recursion and iteration, and when it is appropriate to use each. What geometric shapes called fractals are and how to draw them using recursion. What recursive backtracking is and why it is an effective problem-solving technique. 15.1 Introduction 15.2 Recursion Concepts 15.3 Example Using Recursion: Factorials 15.4 Example Using Recursion: Fibonacci Series 15.5 Recursion and the Method Call Stack 15.6 Recursion vs. Iteration 15.7 Towers of Hanoi 15.8 Fractals 15.9 Recursive Backtracking 15.10 Wrap-Up 15.11 Internet and Web Resources 15.1 Introduction Earlier programs structured as methods that call one another in a disciplined, hierarchical manner Recursive methods Call themselves Useful for some problems to define a method to call itself Can be called directly or indirectly through another method Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text. (Part 1 of 2) Fig. 15.1 | Summary of the 32 recursion examples and exercises in this text. (Part 2 of 2) 15.2 Recursion Concepts Recursive problem-solving elements Base case Recursive method capable of solving only simplest case—the base case If method is called with base case, method returns result If method is called with more .