Programming Questions

Array Addition Recursion

On the Array Addition question this solution works and looks super slick (I can't remember where I found it). But I can't follow it.

function ArrayAdditionI(arr) { arr.sort(function(a,b){ return a - b; }); var largest = arr.pop(); function recursion(target,array){ if(array.length === 0){ return target === 0; } var n = array[0]; array = array.slice(1); return recursion(target,array) || recursion(target - n, array); } return recursion(largest,arr); }At the bottom of the recursion function when it hits the right side of the OR operator it looks like it should just return false. I assume it's some recursive or closure concept that's going over my head. Can anyone explain?

mattlarsh
posted this question on 10/12/14 **|**

14

This question took like 3 days to post, I have found the answer. If anyone is interested stackoverflow.com/questions/26284612/javascript-recursion

mattlarsh

answered on 10/13/14

2

Very elegant solution! I wrapped my head around it when I started to think of the recursive OR statement as branches that produce two more branches for each branch. In that way, we check every permutation of numbers that can be added.
Thanks for sharing, very helpful!

kimeshan

answered on 11/01/14

1

Did a learning blitz on this one and I think I'm getting it. Thanks guys.

rhodesd

answered on 01/25/16

1

I still don't get it. Read the StackOverflow and follow up to: "If you for example have the array [1,2,3,6], let's follow the part of the recursion that finds the solution. The code will first pick out 6 as the largest, then call the recursive function to look for the sum 6 in [1,2,3]."
How exactly does the function check for the sum of 6 in the array[1,2,3] in the first, or any step? I just don't see where the summing and checking is happening. Thanks in advance.

rhodesd

answered on 01/24/16

Log in to write an answer.