Page 818 - Introduction to Programming with Java: A Problem Solving Approach

784 Chapter 15 Files
APPENDIX 8
Recursion
To understand this appendix, you need to be familiar with object-oriented programming and arrays. As such, you need to have read up through Chapter 10.
Recursion is when a method calls itself. What follows is a general approach to solving a task with a recursive implementation.
First, identify a way to make the problem progressively simpler, and identify a condition, called the “stopping condition,” that is associated with the simplest version of the problem. Use an if statement to check for the stopping condition. The if body should contain the solution to the simplest version of the problem. The else body should contain a call(s) to the same method with an argument value(s) that makes the problem progressively simpler. Once the method is called, it automatically continues to call itself with progressively simpler conditions, until its stopping condition is satisfied.
When the stopping condition is satisfied, the method solves the simplest version of the problem. Then it
Apago PDF Enhancer
returns the simplest problem’s solution to the previous method execution at the next higher level of difficulty. That method execution generates the solution to its version of the problem. This process of returning simpler solutions to previous method executions continues back up to the original method execution, which gener- ates the solution to the original problem.
Recursion does not add unique functionality—all recursive algorithms can be converted to loop pro- grams that don’t use recursion. So why use recursion? Because with some problems, a recursive solution is more straightforward than a looping solution. For example, some mathematical concepts, like the factorial of a number and the Fibonacci sequence, are defined recursively, and they lend themselves well to program- matic solutions that use recursion. And some games, like the towers of Hanoi and maze traversals, can be solved best with recursive thinking, and they also lend themselves well to programmatic solutions that use recursion.
Be aware that there is a downside to recursion. Recursive programs tend to be slow because they gener- ate lots of function calls and function calls have lots of overhead. Overhead is work that the computer has to do. For each function call, the computer has to: (1) save the calling module’s local variables, (2) find the method, (3) make copies of call-by-value arguments, (4) pass the arguments, (5) execute the method, (6) find the calling module, and (7) restore the calling module’s local variables. Whew! All that work takes time. That’s why some recursive implementations can be prohibitively slow. For such cases, you should consider rewriting the solution with a loop implementation.
Find the Factorial of a Number
The factorial of a number n is n! 􏰀 n * (n-1) * (n-2) * . . . * 2 * 1. This is an easy problem, and we were able to solve it entirely within the header of an empty for loop in Figure 11.9. So, it’s not really a good candidate for recursion in practice. But because it is easy, it provides a nice introductory illustration of how recursion
784