CODEWITHSUNDEEP
javascriptrecursion
user4851524
user4851524

Reputation:

Need some help to understand recursion

I am trying to understand, how recursion works. I got the basic idea, but the details remain unclear. Here is a simple example in javascript:

function sumTo(n){
    if (n > 1){
        return n + sumTo(n-1)
    } else {
        return n
    }
}

sumTo(3);

It is supposed to count all numbers in 3 and the result is 6 (1 + 2 + 3 = 6), but I don't get, how it works.

OK, we start from if condition. 3 > 1, so we return n and call the function again, but what will be inside if brackets?

Does it look like this:

3 + sumTo(2) // 3 - 1 = 2

Or we don't do anything with n, and wait for the next function:

3 + sumTo(n - 1) // n will come later

I was told that the last function will return 1 to the upper one, but I don't get what it will do with this 1.

If there is some step-by-step explanation for ultimate dummies, please share.

I know there is a lot of similar questions, but found no help.

UPD: It looks like I finally found out how it works, spending two days and asking everyone I could. I'll try to explain for ultimate dummies like me. That's gonna be long, but I hope somebody with the same troubles will find this post and it will be useful.

At first I'd like to show another example of recursion, which is a little easier. I found it at http://www.integralist.co.uk/posts/js-recursion.html and changed values from (1, 10) to (2, 3).

function sum(x, y) {
    if (y > 0) {
      return sum(x + 1, y - 1);
    } else {
      return x;
    }
}

sum(2, 3);

When we start the function, we check the if condition y > 0. Y is 3, so the condition is true. So we return sum(x + 1, y - 1), i. e. sum(2 + 1, 3 - 1), i. e sum(3, 2).

Now we need to count sum(3, 2). Again, we go to the beginning and start from condition y > 0. Y is 2, so the condition is true. So we return sum(x + 1, y - 1), i. e. sum(3 + 1, 2 - 1), i. e sum(4, 1).

Now we need to count sum(4, 1). One more time, we check the condition y > 0. Y is 1, the condition is true. We return sum(x + 1, y - 1), i. e. sum(4 + 1, 1 - 1), i. e sum(5, 0).

Now we need to count sum(5, 0). We check the condition y > 0 and it is false. According to the if-else in the function, we return x, which is 5. So, sum(2, 3) returns 5.

Now let's do the same for sumTo();

function sumTo(n){
    if (n > 1){
        return n + sumTo(n-1)
    } else {
        return n
    }
}

sumTo(3);

Starting from sumTo(3). Checking the n > 1 condition: 3 > 1 is true, so we return n + sumTo(n - 1), i. e. 3 + sumTo(3 - 1), i. e. 3 + sumTo(2).

To go on, we need to count sumTo(2).

To do this, we again start the function from checking the n > 1 condition: 2 > 1 is true, so we return n + sumTo(n - 1), i. e. 2 + sumTo(2 - 1), i. e. 2 + sumTo(1).

To go on, we need to count sumTo(1).

To do this, we again start the function and check the n > 1 condition. 1 > 1 is false, so, according to if-else, we return n, i. e. 1. Thus, sumTo(1) results in 1.

Now we pass the result of sumTo(1) to the upper function, sumTo(2), where we earlier stated that we needed sumTo(1) to go on.

SumTo(2) returns n + sumTo(n-1), i. e. 2 + sumTo(2 - 1), i. e. 2 + sumTo(1), i. e. 2 + 1. Thus, sumTo(2) results in 3.

Now we pass the result of sumTo(2) to the upper function, sumTo(3), where we earlier stated that we needed sumTo(2) to go on.

SumTo(3) returns n + sumTo(n-1), i. e. 3 + sumTo(3 - 1), i. e. 3 + sumTo(2), i. e. 3 + 3. Thus, sumTo(3) finally results in 6. So, sumTo(3) returns 6.

My mistake was that everywhere I tried to insert 3 instead of n, while n was decreasing to 1.

Thanks to everyone, who responded to this question.

Upvotes: 4

Views: 234

Answers (3)

Legotin
Legotin

Reputation: 2688

That's right, sumTo(n) waits until sumTo(n-1) is completed.
So, sumTo(3) waits for sumTo(2),
sumTo(2) waits for sumTo(1),
then sumTo(1) returns 1,
sumTo(2) returns 2 + 1
and sumTo(3) returns 3 + 2 + 1

Upvotes: 2

jaggedsoft
jaggedsoft

Reputation: 4038

Showing work:

sumTo(4) = (4 + 3) + (2 + 1) = 10 // 4 + sumTo(3). function called four times
sumTo(3) = (3 + 2) + 1       = 6  // 3 + sumTo(2). called three times
sumTo(2) = (2 + 1)           = 3  // 2 + sumTo(1). called twice
sumTo(1) = (1)               = 1  // called once

It will probably be easier for you to wrap your head around if you think of it backwards, from the ground up instead of from the top down. Like this:

sumTo(1) = 1 + sumTo(0) = 1
sumTo(2) = 2 + sumTo(1) = 3
sumTo(3) = 3 + sumTo(2) = 6
sumTo(4) = 4 + sumTo(3) = 10

Notice how now you can keep adding to the list, and it will be easy to calculate the previous one because you're just adding the two sums.

The chain of events is as follows:

sumTo(3) adds 3 and calls sumTo(2) which also calls sumTo(1) and returns 3, giving you a grand total of 6.

Does that make sense? I'll gladly elaborate or clarify if anyone has questions. An important question to understand is why to use recursion and when to use recursion. A good discussion on the subject can be found here: When to use recursion?

A classic example of recursion is the fibonacci sequence. Another good example would be traversing a directory of files on your computer, for example if you wanted to search every file inside of a folder that contains other folders. You can also use recursion to factor exponents.

Consider an easier example of recursion:

function multiplyBy10(i) {
    if ( !i ) return 0;
    return 10+multiplyBy10(i-1);
}

This function will multiply the number by 10 using recursion. It's good to get a grasp on when recursion is practical because there are times it makes things easier for you. However, it's best to keep things simple and not confuse yourself wherever possible. :)

Upvotes: 1

Satpal
Satpal

Reputation: 133403

You can understand like

sumTo(3);
returns => 3 +  sumTo(2) // n is greater than 1
                returns => 2 +  sumTo(1)
                                returns => 1 // 1 as n is not greater than 1

Upvotes: 2

Related Questions