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 loops until an item is found or the end parameter is equal or greater than the start variable. The following code snippet shows pseudocode on how we can change this method into a recursive function:
binarySearch(x, array, start, end)
if(start <= end)
mid = (end - start) / 2 + start
if (array[mid] == x) return true
if (array[mid] > x) return binarySearch(x, array, start, mid - 1)
return binarySearch(x, array, mid + 1, end)
return false
Snippet 2.5: Recursive binary search pseudocode
There are actually two stopping conditions in a recursive binary search. The function stops the recursive chain if it either finds the search item at the midpoint or if the start array pointer is greater than the end, meaning the item wasn't found. The stopping condition can easily be found by examining any return paths that don't involve further recursive calls.