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);

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. — joews
– joews, Commented Apr 14, 2017 at 15:03
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 — fg78nc
– fg78nc, Commented Apr 14, 2017 at 15:06
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. — Ted Hopp
– Ted Hopp, Commented Apr 14, 2017 at 15:08
@TedHopp Could not run code at all, so could not use debugger. Thank you for advise. — fg78nc
– fg78nc, Commented Apr 14, 2017 at 15:11
@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. — Barmar
– Barmar, Commented Apr 14, 2017 at 15:12

Barmar · Accepted Answer · 2017-04-14 15:31:08Z

7

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);

edited Apr 14, 2017 at 15:31

answered Apr 14, 2017 at 15:05

Barmar

789k57 gold badges555 silver badges669 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Ted Hopp Over a year ago

OP also doesn't need a return with the recursive call.

fg78nc Over a year ago

Thanks, got it, missed the case.

fg78nc Over a year ago

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 Over a year ago

You use return but not return someExpression, so it doesn't return anything.

fg78nc Over a year ago

I don't mean to return anything, I use return to quit from recursive calls;

|

antonio Musella · Accepted Answer · 2017-04-14 15:10:01Z

0

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);

answered Apr 14, 2017 at 15:10

antonio Musella

5341 gold badge7 silver badges20 bronze badges

1 Comment

Ted Hopp Over a year ago

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.

Collectives™ on Stack Overflow

JavaScript recursion, reversing array

2 Answers 2

9 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related