I’ll try a slightly different approach on this topic.
Let’s change the sum
function so that it’s not recursive. Let’s make it:
function sum(arr, n) {
if (n <= 0) {
return 0;
} else {
return dummy(arr, n - 1) + arr[n - 1];
}
}
I made one change. Now it’s calling a function named dummy
instead of calling itself recursively. It still passes in the same args to dummy
. It still adds the result from dummy
to arr[n-1]
. Everything is exactly the same except that now we call dummy
. And the only thing dummy
does is:
function dummy(arr, n) {
return 0;
}
Now if you call sum([1,2], 2)
, what happens? Well, n
is greater than 0 so we hit the else statement which would execute:
return dummy([1,2], 1) + arr[1]
;
We know what the values in the return statement are. dummy
always returns 0 and arr[1]
is 1, so the return would return the value 1. The point is that the return statement just executes the dummy
function and then adds it to arr[n-1]
. What the dummy
function does is completely independent from what the sum
function does. sum
doesn’t need to know anything about the dummy
function. It just calls it, gets the value, and adds it to arr[n-1]
.
Recursion is just like calling any other function. You call the function, passing in values, and the function returns a value that you can use, just like we did with dummy
. The only difference is that instead of calling dummy
we are calling the function that we are are actually in, we are calling the function itself. But this doesn’t make it any different than calling a different function like dummy
. There is no magic going on here. We are still passing values into the function, getting a result, and then doing something with that result. So you can think of a recursive call to sum
as calling a completely different function that you pass values into and get a result back from.
Now what if our dummy
function above called another function?
function dummy(arr, n) {
return foobar(arr, n - 1) + arr[n-1];
}
We don’t even need to define the new foobar()
function because it’s not important to know what it does. The only thing we care about is that it returns a value that we can use to add to arr[n-1]
and then return a value. So now we have the following:
sum()
calls dummy()
to get a value, which it can then do whatever it wants with to return a value
dummy()
calls foobar()
to get a value, which it can also do whatever it wants with to return a value
Can you see how sum()
has to wait for dummy()
to return a value before it can return a value? And likewise, dummy()
has to wait for foobar()
to return a value before it can return a value? And if foobar()
called a function then it would have to wait for that function to return a value before it could return a value. Each return statement is dependent upon another function to return a value.
Recursion is the same concept. Every time you make a recursive call you are just adding another level of waiting for a function to return a value so that you can do something with that value. Don’t get too hung up on the fact that you are calling the function itself. Even though it has the same name it is really being treated as a completely different function. So with recursion we have:
sum()
calls sum()
(first recursive call) to get a value, which it can then do whatever it wants with to return a value
- the first recursive call to
sum()
calls sum()
(second recursive call) to get a value, which it can then do whatever it wants with to return a value
- the second recursive call to
sum()
calls sum()
(third recursive call) to get a value, which it can then do whatever it wants with to return a value
and so on… Each time we call sum()
we are a starting a new independent function and waiting for its return value. But at some point we’ll need to stop these recursive calls, which is where the base case comes in:
if (n <= 0) {
return 0;
}
Remember that each time we call sum()
we are reducing the second arg by one:
return sum(arr, n-1) + arr[n - 1];
That second arg reduces the value of n
by 1.
So at some point the second arg passed into sum()
will equal 0 and sum()
won’t call itself because it will just return 0. Just like our original dummy()
function above returned 0. That’s what the base case is for in a recursive function, to stop the recursive calls so they don’t go on forever. When we reach the base case then we can finally start getting all those values from the functions we are waiting on to return a value and work our way back up to the first call of sum()
.