Stuck on recursion,

[gabrielrelkovic]

This function is used to make dynamic slices, chunks of a given array.
Every slice is different and therefore a sum of that array chunk as well.
Now what I can’t figure out is the recursion part of it.

I know that we provide the sum(which is 0), then we pass the array and number which presents the length of our array chunks.

let arr = [];
  
function sec(sum, ar, n) {
    if(n == 0) {
      arr.push(sum)
    } else {
      for(let i = 0; i < ar.length; i++) {
        sec(sum + ar[i], ar.slice(1 + i), n - 1);
      }
    }
  }

sec(0, [91, 74, 73, 85], 2);
console.log(arr)  //  [ 165, 164, 176, 147, 159, 158 ] 

So what troubles me the most is how does the function keep recalling itself after the n is equal to 0?
I understand how we get the first num in arr which is 165, but where does function go on from there because n is n == 0 ?

[ilenia]

@gabrielrelkovic

sec(sum + ar[i], ar.slice(1 + i), n - 1);

as n decreases there are various functions that are left open waiting for the function call inside it to finish executing
once n reach 0 all the functions that were left pending start resolving one after the other

[gabrielrelkovic]

Thanks for the reply,
I guess it’s time to really dig in to recursion for the next couple of days.

[kevinSmith]

Yeah, recursion confuses a lot of people.

I’ve been a professional developer for 2.5 years now. I have written one recursive function. I had to explain what it did to a few of the devs. One junior dev didn’t even know what recursion does. (scary) I think recursion gets a disproportionate weight. afaik, it usually only comes into play with certain types of data structures and algorithms, which don’t come up in a lot of web development.

That being said …

It’s still good to learn. It is great exercise for your “algorithm brain”. And it is a great way to show off in interviews.

For me, understanding recursion was more of a visual thing. Understanding what the call stack is can help. Check out youtube and watch all the videos on recursion you can find.

[twotani]

Picture is the best way to understand how the recursion works. Here’s one trace of the sec recursive function. The red labels show the sequence order of the function calls and returns. This one is bit harder to follow of the loop inside the recursion.

You really don’t want to use any global variables with recursive function (actually any function), so you should define a helper function inside a function like this

function sec2(sum, ar, n) {
  let arr = [];

  function helper(sum, ar, n) {
    if (n == 0) {
      arr.push(sum);
    } else {
      for (let i = 0; i < ar.length; i++) {
        helper(sum + ar[i], ar.slice(i+1), n-1);
      }
    }
  }

  helper(sum, ar, n);
  return arr;
}

[gabrielrelkovic]

This visual representation really cleared things out, It’s like that example where in order to find out which row your seat is in the cinema you ask the guy in front of you and he then proceeds to ask the guy in front of him and so that chain goes all the way to the first row, then the guy in the first row turns around and says what row he is in to the guy one row behind him, and that chain now goes all the way back to you and you finally find out what row you are in.

Thanks a lot!

[gabrielrelkovic]

Yeah I kind of get the same feeling but I still want to know at least the basics of recursion So that I don’t become that junior dev who doesn’t even know what recursion is

[kevinSmith]

Yeah, for sure, learn it. But don’t freak out about it and don’t panic if it takes a while to understand - you’re in good company. I think there is value in doing the best you can, moving on, and coming back to it from time to time. Don’t let it hold you back. At some point it will just “click”.

[twotani]

Yes, you got it. You have the right analogy. It “clicked” for you.