javascript recursion basics

Question

I'm trying to learn the concept of recursion, I normally use loops where possible. Can anyone please explain what is happening in this code given the array of numbers.

var set = [1, 2, 3, 4, 5];

function recurs(array) {

if (array.length === 0) {
    return 0;
}
else {
    return array.shift() + recurs(array);
}
  }
    console.log(recurs(set));

I understand the if statement it's basically giving the recursion a chance to end. But I'm confused with what exactly is going on in the else statement, I understand the .shift() function removes the first index of the array but then what exactly? I have run through a debugger and still can't quite get my head around it. The correct answer is 15 I just need to fully understand why. If anyone could break it down for me it would be appreciated.

Barmar · Accepted Answer · 2015-11-18 22:58:47Z

2

array.shift() removes the first element of the array, and also returns that element. So that value then gets added to the result of performing the recursive call. The recursive call then does the same thing with the remaining values of the array. So we start with

recurse([1, 2, 3, 4, 5])

which does:

1 + recurse([2, 3, 4, 5])

which turns into

1 + 2 + recurse([3, 4, 5])

and eventually into:

1 + 2 + 3 + 4 + 5 + recurse([])

In this last case, the if block just returns 0, so the final result is:

1 + 2 + 3 + 4 + 5 + 0

answered Nov 18, 2015 at 22:58

Barmar

789k57 gold badges554 silver badges669 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Brad Christie Over a year ago

much better visual, kudos.

Brad Christie · Accepted Answer · 2015-11-18 22:57:46Z

1

Break it down:

array:         return value (usually shift() + recurs():
[1,2,3,4,5]    1 + (next line, this is the recursive call)
[2,3,4,5]      2                   + "
[3,4,5]        3                   + "
[4,5]          4                   + "
[5]            5                   + "
[]             0 (array.Length==0)

So, basically the result becomes: (1 + (2 + (3 + (4 + (5 + (0)))))) Where each () is an entry into the resurs function.

I'd recommend adding console.log inside the function to see what's incoming, and also store the return value of recurs before returning it and .logging that as well (to give you a better visual).

answered Nov 18, 2015 at 22:57

Brad Christie

102k16 gold badges160 silver badges200 bronze badges

Comments

Nuthan Kumar · Accepted Answer · 2015-11-18 23:02:59Z

1

The shift method removes the element at the zeroeth index and shifts the values at consecutive indexes down, then returns the removed value. If the length property is 0, undefined is returned.

in your example if the length of the array > 0 you are keeping the first element and then calling the method again with rest of array. Break down of your code looks like this

recurs([1,2,3,4,5])
1 + recurs([2,3,4,5])
1 + 2 + recurs ([3,4,5])
1 + 2 + 3 + recurs([4,5])
1 + 2 + 3 + 4 + recurs ([5])
1 + 2 + 3 + 4 + 5 + recurs([])
1 + 2 + 3 + 4 + 5 + 0
15 (results)

answered Nov 18, 2015 at 23:02

Nuthan Kumar

4937 silver badges25 bronze badges

Comments

Icepickle · Accepted Answer · 2015-11-18 23:05:03Z

The MDN exlanation on Array.prototype.shift you can find here. When you remove the first element from the array, it also returns the removed value (or undefined), and it changes the length of the array

In a sense, your function would be very similar to

function sumElements(array) {
   if (!array || array.length === 0) {
       return 0; // full sum
   }
   // get the first value
   var firstValue = array[0];
   // remove it from the array
   array.splice(0, 1);
   return firstValue + sumElements(array); // get the next first value, which happens until the arrays length === 0
}

Your code a bit more clearly written (you don't really need the else there), would be

function recurse(array) {
    if (!array) || array.length === 0) {
        return 0;
    }
    var value = array.shift();
    return value + recurse(array);
}

You of course don't need to get the value like this, it would simply show you in the debugger that

value got assigned with the previous first index of the array
array.length has changed and you are now using the changed array in your recursion

An interesting point to note, is that the array you are sending to your recurse value, will be an empty array after the recursion function, but i'm sure that might be fine in your case (cannot judge it) ;)

Collectives™ on Stack Overflow

javascript recursion basics

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related