Recursive Function - Javascript - sum of array elements equal to n-CodePudding

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:

arr[n-1];

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

CodePudding user response：

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:

== 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

CodePudding user response：

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.

CodePudding user response：

sum([10,20,30,40], 3-1) Will call sum function again, think about it.

CodePudding user response：

Recursive functions usually operate with a value that is immediately accesible and another value that they obtain by calling themselves until a base case is reached.

In this example, that accesible parameter is one of the numbers of an array and the operation is just a simple addition. The base case will be reached when the function's parameters satisfy the if condition.

Think of the different iterations that happen here to understand how the final result is gotten:

First iteration, sum([10,20,30,40], 3)

The if condition is not fulfilled because 3 (n) is greater than 0, so the else branch's code is executed.

We have sum([10,20,30,40], 2) arr[2]. We don't know the result of the recursive call yet but we have the value of the number located in the third position of the array, that is 30 (arrays are usually considered to start from 0).

Second iteration, sum([10,20,30,40], 2)

Again, this is not the base case yet (if branch), so we have:

sum([10,20,30,40], 2-1) arr[2-1] -> sum([10,20,30,40], 1) arr[1] -> sum([10,20,30,40], 1) 20

Third iteration, sum([10,20,30,40], 1)

At this point, we have 30 and 20 as "partial results". These numbers and the results of the remaining iterations will all be added up, because that's what the code in the else branch does, an addition.

sum([10,20,30,40], 1-1) arr[1-1] -> sum([10,20,30,40], 0) arr[0] -> sum([10,20,30,40], 0) 10

Another partial result has been added: 10.

Forth and final iteration, sum([10,20,30,40], 0)

The base case is finally reached, the if branch's code is executed and the recursion stops right here because there isn't another call to the recursive function in this code. The result of sum([10,20,30,40], 0) is 0 because the code returns 0.

Now that we have reached the end of the recursion, we can retrace our steps.

• The result of the third iteration is sum([10,20,30,40], 0) 10. We know this is 0 10 now, so 10.

• The result of the second iteration is sum([10,20,30,40], 1) 20 = 10 20 = 30.

• And the result of the first call and the original call to the function is sum([10,20,30,40], 2) 30 = 30 30 = 60.

Recursive functions are really tricky at first but once you understand this logic of partial results that are "accumulated" until the moment the base case is reached, they get easier. Just take your time.