Need some help to understand recursion

Question

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.

• user663031: we return n and call the function again No. You return the sum of n and the result of calling the function again. I suggest opening your console/debugger, stepping through the code line by line to understand what it is doing.
• Oriol: Better solve the recursion with math and just return n*(n+1)/2
• jmunsch: +1 for the debugger. I personally like to use step into and watch when debuggering: developer.chrome.com/devtools/docs/javascript-debugging
• Shaun: Think of it as algebra. Every time it loops around the value of n changes. Adding to the previous n. If you haven't got a good understanding of the concept of algebra, start there.

Answer 1

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

Answer 2

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

Answer 3

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. :)

• user4851524: I just need to follow this step-by step. So, if each function waits for n everytime, we have the following: 3 > 1, so we return 3 + sumTo(n - 1), and wait for the next sumTo(), right? It looks like next sumTo() deals with 2, so sumTo(2) waits for next sumTo(), which is sumTo(1). 1 > 1 is false, so last function returns 1, but where does it go?
• user824425: pow() is not recursive, or at least not noticeably so.
• jaggedsoft: This recursive pow function has a time complexity of O(logb) I'd be curious if you could find a faster one: pow(a,b) { if(b==0) return 1 temp = pow(a,b/2) if(b%2==0) return(temp * temp) else return(a * temp * temp) }
• jaggedsoft: @qtxt: The original function calls a child function, which in return calls another child function. And none of the functions can complete until it reaches an exit condition where it's finally returning an an actual value. Recursive functions can be hard to understand, it's like the movie inception. I'll update my post with another example, hope it helps. Otherwise, let me know.
• user4851524: @NextLocal: Well, I found some example, which seems understandable, the first block of code here: integralist.co.uk/posts/js-recursion.html It's clear that everytime x is increasing, and y is decreasing, so when we finally call sum (11, 0), y > 0 is false and it just returns x, which is 11. But when there is only one variable it seems much trickier, so I still have troubles despite all efforts.