Understanding recursion

JavaScript
#1

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!

#2

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]?

#3

i think these links will help u understand it


1 Like
#4

Try this article by Beau Carnes

2 Likes
#5

Thank you for great links.

#6

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

#7

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;
}

#8

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
#9

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

1 Like
#10

hahaha geuss we all are here :3

1 Like
#11

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)
#12

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

#13

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

#14

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
#15

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?

#16

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
#17

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

#18