Example case:
function sum(arr, n) {
if (n <= 0) {
return 0;
} else {
return sum(arr, n-1) + arr[n-1];
}
}
(our call 1) sum([5,7,12,4,6,9], 3)
arr n
So we get an array (arr
) of numbers and a number(n
), the number in this case representing that we only want the first three numbers in the array, and we want those numbers added together.
We could write this with a loop another way, but obviously that’s not the point, we are learning recursion. So rather then make a loop we make a function that will return another function, until it hits a base case, the base case being very important, otherwise it would just keep going like a loop without an end and fill the call stack.
So our base case is if (n<=0)
. Less then n
because if we tossed it a negative number the function would keep going because we are eventually going to be subtracting from the value of n
later in our function and would not stop. And equal because if we go to far back n
will hit negative numbers, and since we are using the value of n to grab from the array we are going to have an “undefined” in there, which will break our math.
Since we are doing addition we want our base case to return 0
, because eventually this is the number that is going to be returned at the end of this long line of functions being made and added to the stack, and it is going to be added to all our other array numbers. And remember in this case we only want the first three numbers added together (5,7,12), not all three numbers +1.
Then after that we have an else
. This is the part where we return our function with our array ([5,7,12,4,6,9]) and n-1 (3-1) + a number from the array at arr[n-1] (12). This will eventually give us our base case, but also gives us our numbers in the array to add together.
so return sum([5,7,12,4,6,9], 2) + 12 (our call 2)
is n <= 0
? nope lets do our else
.
return sum([5,7,12,4,6,9], 1) + 7 (our call 3)
is n <= 0
? nope lets do our else.
return sum([5,7,12,4,6,9], 0) + 5 (our call 4)
is n <= 0
? yes! lets finally do the if
and return 0
Now is the part that can get even more confusing. Remember all those functions we made before? They where waiting for an answer, our base case.
so call 4 is getting a return, our 0. So think of sum([5,7,12,4,6,9], 0)
now as equaling 0.
So sum([5,7,12,4,6,9], 0) + 5
is now just 0 + 5. What is 0+5? 5. Remember our call 3? it was waiting on call 4 to finish. So you can think of call 4 now returning 5. what was our call 3? sum([5,7,12,4,6,9], 1) + 7
. So now think of sum([5,7,12,4,6,9], 1)
as just being 5. and remember our +7 in there? what is 5+7?
I could repeat myself for the last one, but you probably get the idea. It keeps going backwards from that point, turning the past functions into numbers and adding them to our array numbers.
And even though we only called sum once, it made a bunch of other ones for us, which then toss back there answers all the way to the original (call 1) with the answer of 24.