Beginning Java Data Structures and Algorithms

Understanding Recursion

Recursion is a really useful tool for algorithm designers. It allows you to solve large problems by solving a smaller occurrence of the same problem. Recursive functions usually have a common structure with the following components:

• One or more stopping conditions: Under certain conditions, it would stop the function from calling itself again
• One or more recursive calls: This is when a function (or method) calls itself

In the next example, we will pick the binary search problem seen in the previous chapter and change the algorithm to work in a recursive manner. Consider the binary search problem discussed in Chapter 1, Algorithms and Complexities, listed in Snippet 1.7. The implementation is iterative, that is, it ...