That’s right.
Okay, now you have one more line but you need to keep going:
sum([1, 3, 4, 5], 2) returns sum([1, 3, 4, 5], 1) + 3
sum([1, 3, 4, 5], 1) returns sum([1, 3, 4, 5], 0) + 1
sum([1, 3, 4, 5], 0) returns ____
sum([1, 3, 4, 5], 0) would then return 0 because n now = 0. This is the base case right? Thanks.
Perfect. So now you can put it all together.
The original call of sum([1, 3, 4, 5], 2) returns
sum([1,3,4,5], 1) + 3
Now we need to get the return value for sum([1,3,4,5], 1) (so we can add it to 3), which is:
sum([1,3,4,5], 0) + 1
Now that we know the return value for sum([1,3,4,5], 1) we can use it in the original return statement for sum([1, 3, 4, 5], 2) which now makes that return statement:
sum([1,3,4,5], 0) + 1 + 3
This is the important step to understand. We merely replaced sum([1,3,4,5], 1) in the original return statement with its return value of sum([1,3,4,5], 0) + 1. This is the recursion. We need to keep calling the function as long as the return value includes another recursive call.
Again, the original return statement is now:
sum([1,3,4,5], 0) + 1 + 3
And we know that sum([1,3,4,5], 0) returns 0 because it’s the base case, so we can substitute that into the original return statement to get:
0 + 1 + 3
Each time we make a recursive call we are just finding one more number to add to the ultimate return value.
2 Likes
Ok thanks both @bbsmooth and @colinthornton
I am sort of getting it but still not sure I’m quite joining the dots.
I think my main point of confusion comes from thinking that the ‘return’ line of code in the function had to be run fully but my realisation is that the function needs run however many times before the first return statement is fully executed. It’s kind of like the first return call is in ‘suspended animation’ until the recursive functions have done their thing and reached 0.
So what about another example…
arr = [5,2,3,6,2] and n = 5 (ie: it’ll sum all the array elements)
so these are these the computations that happen?
return sum([5,2,3,6,2], 4) + 2 // n = 5
return sum([5,2,3,6,2], 3) + 6 // n = 4
return sum([5,2,3,6,2], 2) + 3 // n = 3
return sum([5,2,3,6,2], 1) + 2 // n = 2
return sum([5,2,3,6,2], 0) + 5 // n = 1
return 0 // n = 0
Exactly. The original return statement can’t do anything until it receives a value from the recursive call. But this isn’t any different than if we weren’t using recursion. For example, let’s look at the following return statement:
return getARandomNumber() + 10;
Would you agree with me that this return statement can’t return an actual number until it first calls the function getARandomNumber() and the function returns a number? You don’t need to know anything about how getARandomNumber works. You have no idea if getARandomNumber is calling other functions as well. It doesn’t matter. All you need to know is that getARandomNumber will eventually return a number and the return statement just needs to wait for that function to return a number before it can add that number to 10 and return a final result.
The point is that each recursive function call is really like calling a completely different function. The return statement making the recursive call must wait for the recursive call to return a value. It knows nothing about what the recursive function is doing to return that value. It just sits there and waits until it does.
1 Like
I see. I think the lesson here for me has also been fully understanding how functions work and return statements in general. This is quite a simple example but have found it tricky to work out the steps so God knows how i’ll fare with more complex examples! Is there a way to kind of see the individual steps? I tried putting some console.log methods in at different steps to try and show me what’s going on but it didn’t seem to work as I’d hoped.
Thanks so much for providing such a thoughtful approach for teaching me and for persevering! I very much appreciate it. I’m not sure I’m completely confident with recursion yet but I think it is something i’ll have to come back to frequently and keep practising different examples.
That’s what I would do. Perhaps show us your code with the console logs in there and we might be able to suggest something better?
1 Like
I tried this (using the variables from my original post):
function sum(arr, n) {
if(n <= 0) {
return 0;
} else {
return console.log(sum(arr, n - 1)) + console.log(arr[n - 1]);
}
}
console.log(sum([1,3,4,5], 2));
You can’t mix and match console.log and return like that.
console.log is a function call with a return value of undefined.
Here’s a visualization tool: Python Tutor
Click the “next” button to step through the code line by line. It shows you that there’s a separate frame for each function call.
1 Like
Ok thanks. So can I not use console.log to reveal how the recursion is working then?
That looks very useful, thank you!
You can use console.log, but not in the way you did.
} else {
const recursiveResult = sum(arr, n - 1);
const currentValue = arr[n - 1];
console.log("recursiveResult:", recursiveResult, "currentValue:", currentValue);
return recursiveResult + currentValue;
}
1 Like
A little off topic here, but when I’m log debugging like this I like to throw the variables into an object as a kind of shorthand for a similar result.
console.log({ recursiveResult, currentValue });
1 Like
Hi again folks,
Am afraid having left this alone for a few days, recursion has reared it’s ugly head in a later lesson and I just am not sure I’m getting it yet. The example before the exercise is this:
function countup(n) {
if (n < 1) {
return [];
} else {
const countArray = countup(n - 1);
countArray.push(n);
return countArray;
}
}
console.log(countup(5));
I’ve tried to put some console.logs to help me see what happing in the recursive steps but it’s not outputting anything that makes sense to me. Please could someone help me put some console.logs in this code to demonstrate the recursive steps? Many thanks.
Please share the code you’ve tried.
Generally you want to log before and after some value changes, so you can confirm those changes.
1 Like
Thanks for the reply. I think this is possibly the way to do it:
function countup(n) {
if (n < 1) {
return [];
} else {
const countArray = countup(n - 1);
console.log(n, countArray); // added this
countArray.push(n);
return countArray;
}
}
countup(5);
It outputs:
1 []
2 [ 1 ]
3 [ 1, 2 ]
4 [ 1, 2, 3 ]
5 [ 1, 2, 3, 4 ]
But this doesn’t really illuminate anything to me. Again, my question falls back to my original confusion. How can anything be being added to the array if the array isn’t altered with ‘push’ until after the recursive call? Perhaps a commentary on the console output above line by line would help. Thanks.
When you call a function, it gets run all the way until it hits a return statement. Here’s a kind of pseudo-code representation of the execution line-by-line in order. Each level of indentation is a different function context:
countup(5)
const countArray = countup(4)
const countArray = countup(3)
const countArray = countup(2)
const countArray = countup(1)
const countArray = countup(0)
return []
const countArray = []
countArray.push(1)
return [1]
const countArray = [1]
countArray.push(2)
return [1, 2]
const countArray = [1, 2]
countArray.push(3)
return [1, 2, 3]
const countArray = [1, 2, 3]
countArray.push(4)
return [1, 2, 3, 4]
const countArray = [1, 2, 3, 4]
countArray.push(5)
return [1, 2, 3, 4, 5]
1 Like
Ok but in my example above, at what point does 5 get pushed to the array if (n - 1) happens before the .push method. Eg: This seems to make more sense to me when the 5 gets pushed and then n - 1.
function countup(n) {
if (n < 1) {
return [];
} else {
let countArray = countup(n); //
countArray.push(n); // this would put the 5 into the array?
let countArray = countup(n - 1); // then surely after the above 2 lines, then it goes back to the top of the function?
return countArray;
}
}
countup(5);
When I call countup(1), can you walk me through how the result is [1]?