Understanding recursion

Hi everyone! I am trying to wrap my head around recursion. As I understand it, every recursion call gets saved to the stack until it reaches the base case. Then all the returns from the recursion come into play.

That´s why recursion turns things on its head, like this example that sums values in an array?:

// Creates an array
const range = (start, end) => {
    if (end === start) {
        return [start];
    } else {
        var numbers = range(start, end - 1);
        numbers.push(end);
        return numbers;
    }
};

// Sum numbers in array
const sum = (array) => {
    if (array.length === 0) {
        return 0;
    } else {
        console.log(array);
        var recursion = array[0] + sum(array.slice(1));
        console.log(array);
        return recursion;  
    }
};

console.log(sum(range(1, 10)));

This is the output:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
[ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
[ 3, 4, 5, 6, 7, 8, 9, 10 ]
[ 4, 5, 6, 7, 8, 9, 10 ]
[ 5, 6, 7, 8, 9, 10 ]
[ 6, 7, 8, 9, 10 ]
[ 7, 8, 9, 10 ]
[ 8, 9, 10 ]
[ 9, 10 ]
[ 10 ]
[ 10 ]
[ 9, 10 ]
[ 8, 9, 10 ]
[ 7, 8, 9, 10 ]
[ 6, 7, 8, 9, 10 ]
[ 5, 6, 7, 8, 9, 10 ]
[ 4, 5, 6, 7, 8, 9, 10 ]
[ 3, 4, 5, 6, 7, 8, 9, 10 ]
[ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
55

What I don´t understand is how the first number is 10 when adding the numbers together:
10
19
27
34
40
45
49
52
54
55

Why do we get 10 as the first number?
The code says array[0] + sum(array.slice(1)), and all I can come up with is:

  • If array[0] is 1 and array.slice(1) is 10: 1 + 10 = 11
  • If things are turned on its head and array[0] is 10 and array.slice(1) is 10: 10 + 10 = 20
  • If array[0] is 1 and array.slice(1) is 1: 1 + 1 = 2

Thanks for your help!

I think I actually figured it out after reading my own post :crazy_face:

Does it work like this?
If array[0] is 10 (last item), we slice it off, making the length of the array 0. That is the base case, which returns 0. So it´s 10 + 0?

Then it continues with:
10 + 9
19 + 8
27 + 7 and so on?

But then again, why is it not?:
10 + 0
9 + 9
8 + 8
and so on

How does it retain the correct number in array[0]?

i think these links will help u understand it


1 Like

Try this article by Beau Carnes

2 Likes

Thank you for great links.

Thank you very much. It will be of great help.

Your coding is very good. Can you please help me out. I’m stuck on this exercise.

function exerciseOne(){
// Exercise One: In this exercise you are given an object called ‘mathHelpers’
// Within mathHelpers, create a method called ‘double’
// This method should take one parameter, a number,
// and it should return that number multiplied by two.
mathHelpers =(num){
// Create double method in here.
mathHelpers.double= function(num * 2){
}
return double;
}

this is how i get it

console.log(sum(range(1, 10)));// goes from 1 to 10

so first one goes 
1
1 1+
1 1+ 1++
etc
untile it hits 10 // if (end === start) {
        return [start];
so it ends up into 
10
then it reads
//+ sum(array.slice(1));
10
-10 10
--10 -10 10

Awesome!
I’m on the same lecture, trying to understand Recursion too

1 Like

hahaha geuss we all are here :3

1 Like

Hi. Your code is a bit of topic, but the way I see it is that you are passing in an argument into the object, and inside the object you are referencing a method (mathHelpers.double) that does not exist. The argument should be passed to the method, not the object.

To call this method we would write mathHelpers.double(num)

object = {
  method(param) {function body}
}

let variable = object.method(arg)

@MichaelHelgesen @KittyKora
Btw guys- Did you find the KEY? :smirk:

No as a cat i opened one box and fell asleep XD

To answer your specific question. array.slice creates a new array, so each recurse will have a new shorter array, and on the way back out the previous array comes back into scope. I think that many get confused with the variables in the function having the same name (because of recursion) but the variable/parameter array is referring to a different array with each call to the function.

1 Like

Thank you! That was helpful. I did not think of that.
If I may ask you another question: If local variables are “re-created” with every recurse, is that what´s called closure?

Nope, that’s just local variables. A closure is the set of local variables (sometimes called the “environment”) that a function remembers and keeps a distinct snapshot of when you return that function as a value. The term is often applied to the function itself, which is technically incorrect but close enough.

It’s also used a lot of the time to describe any anonymous function at all, which is totally incorrect, but it’s an entrenched enough term now that there’s no getting around it.

1 Like

Thank you for your answer @chuckadams. I really appreciate it!