Nth index and recursion

JavaScript
2

Yes, most computer languages use zero indexing. This is a hold over from the old days, when you dealt with addresses. You kept the address of the first element and then would use the index to “count in” to find the right element. If your array was at address 1000 and your element was 4 bytes long, your first element was at 1000 + (0 * 4), the second at 1000 + (1 * 4), the next at 1000 + (2* 4) - this is why we think of the first element to be at index 0. It’s a little weird at first, but you’ll get used to it.

So I’m trying to get to grips with the code used for recursions.

Join the club. Yeah, recursion is weird. It’s good to learn but don’t beat yourself up over it. There are a lot of great coders that aren’t strong in recursion. And to be honest, it (at least for me) doesn’t come up much. But when you need it, it will save your life. It also shows up on coding interviews so it is good to know.

Is the code running through the array backwards?

Why not see for yourself?

function sum(arr, n) {
  console.log('n =', n, '   entering sum function');

  if(n <= 0) {
    console.log('n =', n, '   returning', 0);
    return 0;
  } else {
    const val = sum(arr, n-1);
    console.log('n =', n, '   returning', val, '+', arr[n-1]);
    return val + arr[n-1];
  }
}

The output is:

n = 3    entering sum function
n = 2    entering sum function
n = 1    entering sum function
n = 0    entering sum function
n = 0    returning 0
n = 1    returning 0 + 2
n = 2    returning 2 + 3
n = 3    returning 5 + 4
final = 9

It’s kind of hard to explain, but each time it enters the function, it pushes the info for that function call onto the “call stack”. If we haven’t reached the final condition (n <= 0) then it will evaluate sum(arr, n-1)+arr[n-1]. Now in order to do that, it needs to make a new function call. The old function call gets temporarily stalled because it can’t finish until the next call is done. This keeps happening - that’s the first 4 lines of the output. At this point there are 4 incomplete calls to the function.

Then we finally reach our terminal condition and we start “unraveling” the incomplete function calls, returning the values back.

Yeah, it’s weird. It takes a while to get it. I might suggest seeing some youtube videos - there is something to be said about being able to visualize the call stack.

2 Likes