Java™ How to Program, Sixth Edition - Part15

Few weeks back i started reading Java™ How to Program, Sixth Edition By H. M. Deitel - Deitel & Associates, Inc., P. J. Deitel - Deitel & Associates, Inc.

Nice book written By H. M. Deitel - Deitel & Associates, Inc., P. J. Deitel - Deitel & Associates, Inc.

I wanted to share few quotations found the book from the 15th chapter.

1) A recursive method is a method that calls itself directly or indirectly through another method.

2) When a recursive method is called to solve a problem, the method actually is capable of solving only the simplest case(s), or base case(s). If the method is called with a base case, the method returns a result.

3) If a recursive method is called with a more complex problem than a base case, the method typically divides the problem into two conceptual piecesa piece that the method knows how to do and a piece that the method does not know how to do.

4) To make recursion feasible, the piece that the method does not know how to do must resemble the original problem, but be a slightly simpler or smaller version of it. Because this new problem looks like the original problem, the method calls a fresh copy of itself to work on the smaller problemthis is called the recursion step.

5) For recursion to eventually terminate, each time a method calls itself with a simpler version of the original problem, the sequence of smaller and smaller problems must converge on a base case. When, the method recognizes the base case, it returns a result to the previous copy of the method.

6) A recursive call may be a call to another method, which in turn makes a call back to the original method. Such a process still results in a recursive call to the original method. This is known as an indirect recursive call or indirect recursion.

7) Either omitting the base case or writing the recursion step incorrectly so that it does not converge on the base case can cause infinite recursion, eventually exhausting memory. This error is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution.

8) The Fibonacci series begins with 0 and 1 and has the property that each subsequent Fibonacci number is the sum of the preceding two Fibonacci numbers.

9) The ratio of successive Fibonacci numbers converges on a constant value of 1.618..., a number that has been called the golden ratio or the golden mean.

10) Some recursive solutions, such as Fibonacci (which makes two calls per recursion step), result in an "explosion" of method calls.

11) The stack is a data structure whose data objects can be added or removed only at the top of the stack.

12) A stack is analogous to a pile of dishes. When a dish is placed on the pile, it is always placed at the top (referred to as pushing the dish onto the stack). Similarly, when a dish is removed from the pile, it is always removed from the top (referred to as popping the dish off the stack).

13) Stacks are known as last-in, first-out (LIFO) data structuresthe last item pushed (inserted) on the stack is the first item popped (removed) from the stack.

14) Stacks have many interesting applications. For example, when a program calls a method, the called method must know how to return to its caller, so the return address of the calling method is pushed onto the program execution stack (sometimes referred to as the method call stack).

15) The program execution stack contains the memory for local variables on each invocation of a method during a program's execution. This data, stored as a portion of the program execution stack, is known as the activation record or stack frame of the method call.

16) If there are more recursive or nested method calls than can be stored on the program execution stack, an error known as a stack overflow occurs.

17) Both iteration and recursion are based on a control statement: Iteration uses a repetition statement, whereas recursion uses a selection statement.

18) Both iteration and recursion involve repetition: Iteration explicitly uses a repetition statement, whereas recursion achieves repetition through repeated method calls.

19) Iteration and recursion each involve a termination test: Iteration terminates when the loop-continuation condition fails, whereas recursion terminates when a base case is recognized.

20) Iteration with counter-controlled repetition and recursion each gradually approach termination: Iteration keeps modifying a counter until the counter assumes a value that makes the loop-continuation condition fail, whereas recursion keeps producing simpler versions of the original problem until the base case is reached.

21) Both iteration and recursion can occur infinitely: An infinite loop occurs with iteration if the loop-continuation test never becomes false, whereas infinite recursion occurs if the recursion step does not reduce the problem each time in a manner that converges on the base case.

22) Recursion repeatedly invokes the mechanism, and consequently the overhead, of method calls.

23) Any problem that can be solved recursively can also be solved iteratively.

24) A recursive approach is normally preferred over an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug.

25) A recursive approach can often be implemented with few lines of code, but a corresponding iterative approach might take a large amount of code. Another reason to choose a recursive solution is that an iterative solution might not be apparent.

26) The permutations of a string are all the different strings that can be created by rearranging the characters of the original string.

27) Method charAt of class String takes an integer argument and returns the character in the String at that index. As with arrays, the first element of a string is considered to be at position 0.

28) Class String provides two substring methods to enable a new String object to be created by copying part of an existing String object. Each method returns a new String object.

29) If method substring is passed two integer arguments, the first argument specifies the starting index from which characters are copied in the original string, and the second argument specifies the index one beyond the last character to be copied.

30) If method substring is passed one integer argument, the argument specifies the starting index in the original string from which characters are to be copied. The substring returned contains a copy of the characters from the starting index to the end of the string.

31) A fractal is a geometric figure that is generated from a pattern repeated recursively an infinite number of times. The figure grows by adding the pattern at different orientations and scaling to the original.

32) Fractals have a self-similar propertywhen subdivided into parts, each is a reduced-size copy of the whole.

33) The process of using recursion to return to an earlier decision point is known as recursive backtracking. If one set of recursive calls does not result in a solution to the problem, the program backs up to the previous decision point and makes a different decision, often resulting in another set of recursive calls.

About the Authors

Dr. Harvey M. Deitel, Chairman and Chief Strategy Officer of Deitel & Associates, Inc., has 43 years experience in the computing field, including extensive industry and academic experience. Dr. Deitel earned B.S. and M.S. degrees from the Massachusetts Institute of Technology and a Ph.D. from Boston University. He worked on the pioneering virtual-memory operating-systems projects at IBM and MIT that developed techniques now widely implemented in systems such as UNIX, Linux and Windows XP. He has 20 years of college teaching experience, including earning tenure and serving as the Chairman of the Computer Science Department at Boston College before founding Deitel & Associates, Inc., with his son, Paul J. Deitel. He and Paul are the co-authors of several dozen books and multimedia packages and they are writing many more. With translations published in Japanese, German, Russian, Spanish, Traditional Chinese, Simplified Chinese, Korean, French, Polish, Italian, Portuguese, Greek, Urdu and Turkish, the Deitels' texts have earned international recognition. Dr. Deitel has delivered hundreds of professional seminars to major corporations, academic institutions, government organizations and the military.

Paul J. Deitel, CEO and Chief Technical Officer of Deitel & Associates, Inc., is a graduate of the MIT's Sloan School of Management, where he studied Information Technology. Through Deitel & Associates, Inc., he has delivered Java, C, C++, Internet and World Wide Web courses to industry clients, including IBM, Sun Microsystems, Dell, Lucent Technologies, Fidelity, NASA at the Kennedy Space Center, the National Severe Storm Laboratory, Compaq, White Sands Missile Range, Rogue Wave Software, Boeing, Stratus, Cambridge Technology Partners, Open Environment Corporation, One Wave, Hyperion Software, Adra Systems, Entergy, CableData Systems and many other organizations. Paul is one of the most experienced Java corporate trainers having taught about 100 professional Java training courses. He has also lectured on C++ and Java for the Boston Chapter of the Association for Computing Machinery. He and his father, Dr. Harvey M. Deitel, are the world's best-selling Computer Science textbook authors.