I am working my way through the javascript course on freecodecamp and im confused with the lesson on recursive functions.
I am having difficulty understanding the following code:
function sum(arr, n) {
if(n<=0) {
return 0;
} else {
return sum(arr, n-1) + arr[n-1];
}
}
sum([10,20,30,40], 3);
The specific part im struggling with is this:
would the return line not be returning sum([10,20,30,40], 3-1) + arr[3-1] resulting in 30+30 = 60?
Any help with this would be greatly appreciated. Or even pointing me in the right direction to look into this further.
Thanks
Let's write the original code in a more intuitive way by putting arr[n-1] first. This way we can keep expanding each call to sum() to the right.
But first let's note down what sum(arr, n) call will return for each n
if n > 0 => arr[n-1] + sum(arr, n-1)
if n == 0 => 0
n == 3 => arr[2] + sum(arr, 2)
n == 2 => arr[1] + sum(arr, 1)
n == 1 => arr[0] + sum(arr, 0)
n == 0 => 0
Now we expand our steps:
sum(arr, 3)
== arr[2] + sum(arr, 2) // expand sum(arr,2) where n = 2
== arr[2] + arr[1] + sum(arr, 1) // expand sum(arr,1)
== arr[2] + arr[1] + arr[0] + sum(arr,0) // expand sum(arr,0)
== arr[2] + arr[1] + arr[0] + 0
== 30 + 20 + 10 + 0
Test with
function sum(arr, n) {
console.log(`calling sum(arr, ${n})`);
if(n<=0) {
console.log(`returning 0`);
return 0;
} else {
console.log(`calculating [sum(arr, ${n-1}) + ${arr[n-1]}]`);
let s = sum(arr, n-1);;
console.log(`returning [sum(arr, ${n-1}) + ${arr[n-1]}] = [${s} + ${arr[n-1]}]`);
return s + arr[n-1];
}
}
sum([10,20,30,40], 3);
The output will be:
calling sum(arr, 3)
calculating [sum(arr, 2) + 30]
calling sum(arr, 2)
calculating [sum(arr, 1) + 20]
calling sum(arr, 1)
calculating [sum(arr, 0) + 10]
calling sum(arr, 0)
returning 0
returning [sum(arr, 0) + 10] = [0 + 10]
returning [sum(arr, 1) + 20] = [10 + 20]
returning [sum(arr, 2) + 30] = [30 + 30]
Two other classic examples of simple recursive functions are factorial and fibonacci, because those two formulas itself are recursive. Multiplication could also be computed recursively, if you think as a * b being a + (a + ...) where a is added b times.
If you're trying to code those functions, there's a hint to code this last example:
5 * 10 is equal to 5 + 5 * 9, which is equal to 5 + 5 + 5 * 8 and so on.
sum([10,20,30,40], 3-1) Will call sum function again, think about it.