3.10: Recursive Version
- Page ID
- 20807
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Another way to write a binary search is with a recursive method. The trick is to write a method that takes low
and high
as parameters, and turn steps 3 and 4 into recursive invocations. Here’s what the code looks like:
public static int binarySearch(Card[] cards, Card target, int low, int high) { if (high < low) { return -1; } int mid = (low + high) / 2; // step 1 int comp = cards[mid].compareTo(target); if (comp == 0) { // step 2 return mid; } else if (comp < 0) { // step 3 return binarySearch(cards, target, mid + 1, high); } else { // step 4 return binarySearch(cards, target, low, mid - 1); } }
Instead of a while
loop, we have an if
statement to terminate the recursion. If high
is less than low
, there are no cards between them, and we conclude that the card is not in the array.
Two common errors in recursive programs are (1) forgetting to include a base case, and (2) writing the recursive call so that the base case is never reached. Either error causes infinite recursion and a StackOverflowException
.