Seinfeld - 10 months ago 50

Java Question

Lately, I realized that I don't get the recursion as much as I thought so. That's why I'm trying to find as many examples as possible to figure it out, but I got caught very fast.

It's simple Binary Search code that works, yet I have very hard time understanding the recursion part. Especially because I don't see how anything changes with each further step. If at any point there was +1 or -1 given to any of variables, I might get it, but here variables are passed naturally, without any changes.

`public class BinarySearchRecursion {`

public static int binarySearch(int[] array, int value, int start, int end) {

if ((end - start) <= 1) {

if (array[start] == value)

return start;

if (array[end] == value)

return end;

return -1;

}

int midPoint = (start + end) / 2;

if (array[midPoint] > value) {

return binarySearch(array, value, 0, midPoint);

} else {

return binarySearch(array, value, midPoint, end);

}

}

public static void main(String[] args) {

int[] a = { 4, 9, 10 };

System.out.println(binarySearch(a, 10, 0, a.length - 1));

}

}

Answer Source

You seem to be misled by thinking that the parameter called `start`

is the same variable throughout the different recursive calls - but this is *not* the case (and similarly for `end`

). There is *no* direct connection between the value of a particular parameter in different recursive calls, even though it's got the same name. Instead, the parameter values are passed *by position*: when you call `binarySearch`

, whatever expression you write in the third parameter position will become the value of `start`

in the new call.

So if `array[midPoint] > value`

is true, you'll call `binarySearch(array, value, 0, midPoint)`

, which is actually a bug - it's supposed to be `binarySearch(array, value, start, midPoint)`

. This means that in the new call, the value of `start`

will be the same as in this call, but the value of `end`

will be the value that this call computed for `midPoint`

. Otherwise, you'll call `binarySearch(array, value, midPoint, end)`

, so that in the new call, the value of `start`

will be `midPoint`

, and the value of `end`

will be the same as in this call.

(This goes for all methods, not just recursive ones. Also, note that `array`

and `value`

*do* keep their values throughout the recursive calls, but that's because you "pass them to themselves" in the first and second parameter position.)