Nth index and recursion

Tell us what’s happening:
Hi

So I’m trying to get to grips with the code used for recursions.
I don’t even have enough of an understanding to write this code out if left it for an hour and came back.

So below in the code: if( n <= 0 ) {
return 0}

How does zero indexing work here? Is 0 the first element of the array?

Is the code running through the array backwards?

  **Your code so far**

function sum(arr, n) {
// Only change code below this line
if(n <= 0) {
return 0;
}else{
return sum(arr, n-1)+arr[n-1]
}
}
// Only change code above this line

  **Your browser information:**

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/89.0.4389.90 Safari/537.36 Edg/89.0.774.57.

Challenge: Replace Loops using Recursion

Link to the challenge:

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

Hi Kevin

Thanks for getting back. To be honest I didn’t try and figure it out to that depth. I can grasp the idea I think of an infinite loop as such. The problem I’m having and it seems to be quite common is the actual code itself.

I don’t get sum(arr, n) == sum(arr, n-1)+arr[n-1]. To me this seem that if n = 3, I would get (3-1) + (3-1) which would give 4 in the instance of addition so, I am really struggling with this.

I would really appreciate any help you could me on this. I have spent 2 days at this so far.

Although I got the exercise correct, if I left it for a bit and came back to it I would surely not remember it as I actually don’t understand it.

Thanks

No, you don’t just pick out numbers you can see in the code and randomly add them together.

sum(arr, 3-1) is the result of whatever that function produces, it’s not the same as 3-1. And arr[3-1] is the third element of the array arr, it’s not the same as 3-1. JavaScript (and maths) do not behave differently when recursion is involved.

So say arr is [2,3,4,5] and n is 3.
n is not 0
return sum([2,3,4,5], 3-1) + [2,3,4,5][3-1]
which is sum([2,3,4,5], 2) + 4

So evaluate sum([2,3,4,5], 2)
arr is [2,3,4,5] and n is 2.
n is not 0
return sum([2,3,4,5], 2-1) + [2,3,4,5][2-1]
which is sum([2,3,4,5], 1) + 3

So we now have sum([2,3,4,5], 1) + 3 + 4

So evaluate sum([2,3,4,5], 1)
arr is [2,3,4,5] and n is 1.
n is not 0
return sum([2,3,4,5], 1-1) + [2,3,4,5][1-1]
which is sum([2,3,4,5], 0) + 2

So we now have sum([2,3,4,5], 0) +2 + 3 + 4

So evaluate sum([2,3,4,5], 0)
arr is [2,3,4,5] and n is 0.
n is 0
return 0

So we now have 0 + 2 + 3 + 4

2 Likes

Well, read through Dan’s excellent reply. That was going to be my next step.

I have spent 2 days at this so far.

Only two days? Don’t worry about that. Heck, I wrote a recursive function last year (I think it was the only professional recursive function). One junior dev didn’t even know what recursion was. There were a few other devs that didn’t understand how it worked - and this was a pretty simple one. These were professional devs! Like I said, don’t be too hard on yourself - this is a confusing subject for a lot of people.

And like I said, I would recommend watching some (several) youtube videos on the subject. For me at least, there is something visual about recursion. I remember when I was studying computers in high school (in Pascal - yes, that’s how old I am). I could kind of do it but really didn’t understand it. Then I remember I was home one night lazily doing a pagoda puzzle. I was trying to figure out if there was a methodical, algorithmic approach. I found one. Then I literally stood up and back in shock - it was recursion.

Don’t beat up on yourself. If you can’t get it at this point, put it aside for a bit and come back later.

Like I said, there are a lot of devs out there that aren’t good at recursion (myself included.) And the good thing is that for most web devs it doesn’t come up that much. It tends to only come up on certain kinds of problems. And there is no recursive problem that can’t be solved iteratively. In fact, often the iterative solution is better. (I’ve seen devs try to show of with complex recursive solutions to simple problems.) But for certain kinds of problems, usually involving certain types of complex data structures, a recursive solution can be quite elegant. But you’re probably a long way from needing them.

Set a time limit for how much time you’re going to spend on this and come back to it later. It’s important that you learn the basics of recursion, but it’s not important that you master it right now.

1 Like

It seems to me that this is a poor example of recursion. Why is arr carried through all the levels of recursion when it doesn’t change? It would be better left out in the global scope. In fact, I would think that a for…next loop would be the natural way to approach the computation.

A classic demo of recursion is factorial, although that could also be done with a for…next loop. An application where recursion is necessary is traversing tree structures.

This factorial example may be helpful:

  console.log("Main", factorial(3));
function factorial(n) {
  let vreturn; // for console.log
  if (n==0) vreturn = 1;
  else vreturn = n*factorial(n-1);
  console.log("fac", n, vreturn);
  return vreturn;
}

Yeah, some of these aren’t the best examples. Sometimes it’s like using an aircraft carrier to go water skiing - there is a simpler solution. But you have to start somewhere and a lot of recursion problems can get quite abstract very quickly - it’s hard to come up with simple one dimensional ones. I would guess that they chose to do this problem because the factorial problem is already done to death and they wanted something different.

As to keeping the array global - many of us would avoid that because we avoid global variables and because we like writing pure functions.

I understand where you’re coming from, but I don’t think factorial is a good example: it’s always used as an example because it demonstrates you can map 1-to-1 from a mathematical definition to programming, but that isn’t practical either (and is more abstract than working on an array), it’s just elegant.

2 Likes

I strongly disagree. We have enough instances of learners making a mess of recursion because they are using global variables. Adding an example that uses global variables would make it worse.

1 Like

You should definitely not carry “arr” up and down the recursion chain.

  1. It does not change, and just adds to call stack space and processing.
  2. It makes it confusing for readability (why is arr a parameter?)
  3. To denigrate global seems arbitrary – the global scope has as much value as any.

But, I should have said “left in a wider scope” instead of “left out in the global scope”.

To be fair, this isn’t the best use case for recursion; I’d use a high order method.

And to be pedantic, you are only carrying a pointer to the array up and down the call stack rather than the entire array. Pointers are small.

But to my point, hard coding a reference to an array in the global (or a higher level) scope

  1. breaks the entire purpose of reusable functions
  2. confuses our learners who already struggle to properly understand scope in recursion

And I’m not a big fan of making an inner recursive function that references a variable in the scope of an outer function. That’s just an obsfugated while loop. That sort of thing is just harder to reason about and maintain.

I would not show an example of a recursive function referencing a single global array. We have to help learners fix their code after writing broken faux-recursion that uses a global result array frequently, and an example using a global variable would only make it worse.

1 Like

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.