Recursion Practice: Nested Addition

[00:00:00]
>> So another really good use case for and this would work iteratively as well the recursive this would be a really cool solution. Let's say you had all of these numbers here and they were arbitrarily nested, right, like you can see here, this 14 here is pretty nested.

[00:00:15]
You can write this as iterative and you can unwrap arrays and things like that. You could also just call a recursive add call on all of these, and these would work really well. So let's actually give you a shot at doing this. So I'm gonna go edit here on SandBox.

[00:00:37]
And we're gonna pop over to code sandbox here. And we're gonna go to files. And we're gonna go to nested edition. So it's in recursion. There's one here called nested arrays.test.js. And what I want you to do is I want you to go and write code in a recursive fashion that takes all the numbers in the array and adds them together, right.

[00:01:11]
So this should be 10 + 12 + 14 +1 + 16 + 20 + 10 + 11. And I want you to use recursion. So one you can definitely use flat and that's cheating. Do not use flatten for this, or flat or smush depending on when you started writing JavaScript, but I don't want you to do that.

[00:01:41]
I want you to write this with recursion, so we're gonna give you just a bit of time for this. But just think about first what's your base case? In this case your base cases if you're adding a number right and not adding an array of arrays when you recurse more, right?

[00:01:58]
And then yeah, then you can just go into return a number at the end. I remember the first time I learned recursion and I was a buddy young lad young strapping lad in Bountiful, Utah. My brother would make me write code before I could play video games. And just the moment that it clicked for me is wait, I call the function inside of itself, the call is coming from inside the function.

[00:02:30]
That's funnier than I thought it'd be. Anyway, I don't know. It just melts my mind. It made me feel like I had superpowers. So it was cool experience for me. Hopefully it's a cool experience for you. Imagine some of you probably have written recursive functions before but for some of you might be a really cool experience.

[00:02:48]
All right, so I'm gonna have ,let some function, equals 0, and I'm gonna say 4 let i equals zero, i is less than array.length. I plus, plus And I'm going to say const current = array[i]. And then I'm going to say if array.isarray. This is just a nice little helper function that lets you check if something's an array.

[00:03:35]
Then we need to recurse, right? So when I say sum, plus equals, whatever comes back from nested add of current, right? Else otherwise it's the number you can assume it's always a number. Sum plus equals current and we keep on our merry way with our for loop. Then down here we're gonna say return sum.

[00:04:07]
So our base case, interestingly enough is not at the top. I would say frequently is at the top. I would say usually is at the top. But in this particular case, it wasn't, okay, but the base case is here, which is to say that it's not an array.

[00:04:23]
Right and then we keep going. And then here you can see it's gonna come down with the nested data and it's gonna call this again and again until we eventually get our answer. So let's try this, make sure that it works the way that we think it should.

[00:04:44]
And recursion, nested arrays, and it works. Now you absolutely totally could do this with iteration and just on unpacking arrays that way, but this is actually a nice elegant solution that we use this nested add function and I would say this is totally fine. You might get a little bit more performance out of a Iterative solution, but even for pretty deep arrays this should be plenty fine.

[00:05:21]
So any questions about nested AP?
>> What would be the time complexity for this?
>> Good question. The time complexity.
>> [INAUDIBLE]
>> Yeah, so what's the time complexity of our solution here? This is an interesting one to model because the depth of the recursion is not gonna be dependent on how long the array is, but the depth of the recursion is gonna be determined by how nested these arrays are, right?

[00:06:03]
So you can see here this only has of length one but it's nested a whole bunch, right? So we'd actually probably have to introduce some sort of third variable here or second variable. So we have n, typically the next thing you introduce is k, right? So this would probably be of complexity n because we would have certainly have to link loop over everything in the array, plus we'd probably have to times it by k, which would be the depth of recursion.

[00:06:32]
So n k probably might need to check me on that one. It's kind of hard to model some of these things as big O because some of them don't lend themselves super well the big O analysis but that would be my guess