TAILIEUCHUNG - Lecture An introduction to computer science using java (2nd Edition): Chapter 14 - S.N. Kamin, D. Mickunas, E. Reingold

In this chapter we will: introduce recursion as a programming technique, show how recursion can be used to simplify the design of complex algorithms, present several well known recursive algorithms (. quicksort, merge sort, Guaussian elmination), introduce the linked list data structure and recursive implementations for several of its methods, present programs for drawing two types of fractal curves. | Chapter 14 Recursion Lecture Slides to Accompany An Introduction to Computer Science Using Java (2nd Edition) by . Kamin, D. Mickunas, , E. Reingold Chapter Preview In this chapter we will: introduce recursion as a programming technique show how recursion can be used to simplify the design of complex algorithms present several well known recursive algorithms (. quicksort, merge sort, Guaussian elmination) introduce the linked list data structure and recursive implementations for several of its methods present programs for drawing two types of fractal curves Recursion Basic problem solving technique is to divide a problem into smaller subproblems These subproblems may also be divided into smaller subproblems When the subproblems are small enough to solve directly the process stops A recursive algorithm is a problem solution that has been expressed in terms of two or more easier to solve subproblems Counting Digits Recursive definition digits(n) = 1 if (–9 <= n <= 9) 1 + digits(n/10) otherwise Example digits(321) = 1 + digits(321/10) = 1 +digits(32) = 1 + [1 + digits(32/10)] = 1 + [1 + digits(3)] = 1 + [1 + (1)] = 3 Counting Digits in Java int numberofDigits(int n) { if ((-10 < n) && (n < 10)) return 1 else return 1 + numberofDigits(n/10); } Recursion If you want to compute f(x) but can’t compute it directly Assume you can compute f(y) for any value of y smaller than x Use f(y) to compute f(x) For this to work, there has to be at least one value of x for which f(x) can be computed directly (. these are called base cases) Evaluating Exponents Recurisivley static int power(int k, int n) { // raise k to the power n if (n == 0) return 1; else return k * power(k, n – 1); } Divide and Conquer Using this method each recursive subproblem is about one-half the size of the original problem If we could define power so that each subproblem was based on computing kn/2 instead of kn – 1 we could use the divide and conquer principle Recursive divide and conquer algorithms

• Kỹ thuật lập trình
• Computer science
• Computer science using Java
• Programming using Java
• Java programming
• Counting digits
• Counting digits in Java
• Engineering Department
• Computer Scienc
• Feaculty of Computer Science
• remove the median element
• computer architecture
• computer engineering
• PhD thesis Computer science and technology
• Optical communication
• Computer science and electronic engineering
• Computer science and technology
• Detection optical OFDM system
• Optical OFDM
• Computer Literacy
• Lecture Computer literacy
• Introduction to computers
• Computer applications
• Computer Networks
• Computer Ethics
• Journal of technology and science education
• Making Capstone project a holistic learning experience
• Students of undergraduate computer science engineering program
• Undergraduate computer science engineering programs
• The stakeholders like companies
• Object Oriented Programming
• Computer organization
• Quantum computer science
• Quantum computer science: An introduction
• Quantum computer
• Circuit diagrams
• Number theoretic preliminaries
• Quantum error correction
• transaction processing
• database
• information management
• computer tricks
• computer skills
• informatics reference materials
• computer software
• computer science advanced
• teaching computer science
• programming C
• Transferring images
• Luận văn Thạc sĩ
• Tóm tắt luận văn Thạc sĩ
• Quản trị kinh doanh
• Summary of dissertation Computer science
• Distributed virtual host system
• Deadlock prevention
• Resource allocation
• Abstract Windowing Toolkit
• Mouse events
• Java packages
• Application programmer interface
• Layout managers
• UML notation
• Sequential files
• Wrapper classes
• Program elements
• OutputBox class
• Data types
• Fundamental data types of Java