JavaScript recursion, reversing array

Question

I can't understand why the following code snippet leads to error. Any ideas?

Maximum call stack size exceeded

function reverseArrayInPlace(array, low, high) {
 if (low == undefined) {
 low = 0;
 }
 if (high == undefined) {
 high = array.length - 1;
 }
 if (low >= high) {
 return;
 }
 var temp = array[low];
 array[low] = array[high];
 array[high] = temp;
 return reverseArrayInPlace(array, low++, high--);
}
var arrayValue = [1, 2, 3, 4, 5];
reverseArrayInPlace(arrayValue);
console.log(arrayValue);

• joews: That means your base case, if (low >= high) isn't being hit. You always fall through to the recursive case, which the JS engine eventually blocks because otherwise it would go on forever. Maybe that will help you debug the algorithm.
• fg78nc: Yes, true, base case is not hit, questions is why exactly, low is incremented with each call, and high is decremented, eventually there has to point for condition of low >= high to be true
• Ted Hopp: You should learn to use a debugger to track down problems like this. Or at least put in some console.log calls to track what values are being passed in.
• fg78nc: @TedHopp Could not run code at all, so could not use debugger. Thank you for advise.
• Barmar: @TedHopp I suspect that he could spend hours in the debugger and he'd never have figured out why the recursive call wasn't passing in the expected values.

Answer 1

It's because you're using post-increment and post-decrement. It increments/decrements the variable, but returns the old value, so you're passing the old value in the recursion. As a result, the recursive call is identical to the original call, and you recurse infinitely.

Pre-increment/decrement -- ++low and --high -- would work correctly. But you don't need to update the variables at all, since you never use them again. Just do normal addition/subtraction.

There's also no point in using return reverseArrayInPlace() when you make the recursive call, because the base case doesn't return anything. Just make the recursive call without putting it in a return statement.

function reverseArrayInPlace(array, low, high) {
 if (low == undefined) {
 low = 0;
 }
 if (high == undefined) {
 high = array.length - 1;
 }
 if (low >= high) {
 return;
 }
 var temp = array[low];
 array[low] = array[high];
 array[high] = temp;
 reverseArrayInPlace(array, low + 1, high - 1);
}
var arrayValue = [1, 2, 3, 4, 5];
reverseArrayInPlace(arrayValue);
console.log(arrayValue);

• Ted Hopp: OP also doesn't need a return with the recursive call.
• fg78nc: Thanks, got it, missed the case.
• fg78nc: There's also no point in using return when you make the recursive call, because the base case doesn't return anything. Could you please clarify - I am using return in base case just to quit function.
• Barmar: You use return but not return someExpression, so it doesn't return anything.
• fg78nc: I don't mean to return anything, I use return to quit from recursive calls

Answer 2

because you have to use ++low and --high in the recursive call. in your version the values are first passed and then modified.

function reverseArrayInPlace(array, low, high) {
 if (low == undefined) {
 low = 0;
 }
 if (high == undefined) {
 high = array.length - 1;
 }
 if (low >= high) {
 return;
 }
 var temp = array[low];
 array[low] = array[high];
 array[high] = temp;
 return reverseArrayInPlace(array, ++low, --high);
}
var arrayValue = [1, 2, 3, 4, 5];
reverseArrayInPlace(arrayValue);
console.log(arrayValue);

• Ted Hopp: Using pre-increment and pre-decrement is a waste; those variables are dead after the recursive call. Just recurse with low + 1 and high - 1.