Recursion is a tricky topic to understand and I don't think I can fully do it justice here. Instead, I'll try to focus on the particular piece of code you have here and try to describe both the intuition for why the solution works and the mechanics of how the code computes its result.
The code you've given here solves the following problem: you want to know the sum of all the integers from a to b, inclusive. For your example, you want the sum of the numbers from 2 to 5, inclusive, which is
2 + 3 + 4 + 5
When trying to solve a problem recursively, one of the first steps should be to figure out how to break the problem down into a smaller problem with the same structure. So suppose that you wanted to sum up the numbers from 2 to 5, inclusive. One way to simplify this is to notice that the above sum can be rewritten as
2 + (3 + 4 + 5)
Here, (3 + 4 + 5) happens to be the sum of all the integers between 3 and 5, inclusive. In other words, if you want to know the sum of all the integers between 2 and 5, start by computing the sum of all the integers between 3 and 5, then add 2.
So how do you compute the sum of all the integers between 3 and 5, inclusive? Well, that sum is
3 + 4 + 5
which can be thought of instead as
3 + (4 + 5)
Here, (4 + 5) is the sum of all the integers between 4 and 5, inclusive. So, if you wanted to compute the sum of all the numbers between 3 and 5, inclusive, you'd compute the sum of all the integers between 4 and 5, then add 3.
There's a pattern here! If you want to compute the sum of the integers between a and b, inclusive, you can do the following. First, compute the sum of the integers between a + 1 and b, inclusive. Next, add a to that total. You'll notice that "compute the sum of the integers between a + 1 and b, inclusive" happens to be pretty much the same sort of problem we're already trying to solve, but with slightly different parameters. Rather than computing from a to b, inclusive, we're computing from a + 1 to b, inclusive. That's the recursive step - to solve the bigger problem ("sum from a to b, inclusive"), we reduce the problem to a smaller version of itself ("sum from a + 1 to b, inclusive.").
If you take a look at the code you have above, you'll notice that there's this step in it:
return a + sumInts(a + 1, b: b)
This code is simply a translation of the above logic - if you want to sum from a to b, inclusive, start by summing a + 1 to b, inclusive (that's the recursive call to sumInts), then add a.
Of course, by itself this approach won't actually work. For example, how would you compute the sum of all the integers between 5 and 5 inclusive? Well, using our current logic, you'd compute the sum of all the integers between 6 and 5, inclusive, then add 5. So how do you compute the sum of all the integers between 6 and 5, inclusive? Well, using our current logic, you'd compute the sum of all the integers between 7 and 5, inclusive, then add 6. You'll notice a problem here - this just keeps on going and going!
In recursive problem solving, there needs to be some way to stop simplifying the problem and instead just go solve it directly. Typically, you'd find a simple case where the answer can be determined immediately, then structure your solution to solve simple cases directly when they arise. This is typically called a base case or a recursive basis.
So what's the base case in this particular problem? When you're summing up integers from a to b, inclusive, if a happens to be bigger than b, then the answer is 0 - there aren't any numbers in the range! Therefore, we'll structure our solution as follows:
- If a > b, then the answer is 0.
- Otherwise (a ≤ b), get the answer as follows:
- Compute the sum of the integers between a + 1 and b.
- Add a to get the answer.
Now, compare this pseudocode to your actual code:
func sumInts(a: Int, b: Int) -> Int {
if (a > b) {
return 0
} else {
return a + sumInts(a + 1, b: b)
}
}
Notice that there's almost exactly a one-to-one map between the solution outlined in pseudocode and this actual code. The first step is the base case - in the event that you ask for the sum of an empty range of numbers, you get 0. Otherwise, compute the sum between a + 1 and b, then go add a.
So far, I've given just a high-level idea behind the code. But you had two other, very good questions. First, why doesn't this always return 0, given that the function says to return 0 if a > b? Second, where does the 14 actually come from? Let's look at these in turn.
Let's try a very, very simple case. What happens if you call sumInts(6, 5)? In this case, tracing through the code, you see that the function just returns 0. That's the right thing to do, to - there aren't any numbers in the range. Now, try something harder. What happens when you call sumInts(5, 5)? Well, here's what happens:
- You call
sumInts(5, 5). We fall into the else branch, which return the value of `a + sumInts(6, 5).
- In order for
sumInts(5, 5) to determine what sumInts(6, 5) is, we need to pause what we're doing and make a call to sumInts(6, 5).
sumInts(6, 5) gets called. It enters the if branch and returns 0. However, this instance of sumInts was called by sumInts(5, 5), so the return value is communicated back to sumInts(5, 5), not to the top-level caller.sumInts(5, 5) now can compute 5 + sumInts(6, 5) to get back 5. It then returns it to the top-level caller.
Notice how the value 5 was formed here. We started off with one active call to sumInts. That fired off another recursive call, and the value returned by that call communicated the information back to sumInts(5, 5). The call to sumInts(5, 5) then in turn did some computation and returned a value back to the caller.
If you try this with sumInts(4, 5), here's what will happen:
sumInts(4, 5) tries to return 4 + sumInts(5, 5). To do that, it calls sumInts(5, 5).
sumInts(5, 5) tries to return 5 + sumInts(6, 5). To do that, it calls sumInts(6, 5).sumInts(6, 5) returns 0 back to sumInts(5, 5).</li>
<li>sumInts(5, 5)now has a value forsumInts(6, 5), namely 0. It then returns5 + 0 = 5`.
sumInts(4, 5) now has a value for sumInts(5, 5), namely 5. It then returns 4 + 5 = 9.
In other words, the value that's returned is formed by summing up values one at a time, each time taking one value returned by a particular recursive call to sumInts and adding on the current value of a. When the recursion bottoms out, the deepest call returns 0. However, that value doesn't immediately exit the recursive call chain; instead, it just hands the value back to the recursive call one layer above it. In that way, each recursive call just adds in one more number and returns it higher up in the chain, culminating with the overall summation. As an exercise, try tracing this out for sumInts(2, 5), which is what you wanted to begin with.
Hope this helps!
LearnYouARecursion, complete problem sets from world-class professor! – recursion.ninja