Unable to understand how this recursive function evaluates-CodePudding

Please help me understand how the following code always returns the smallest value in the array. I tried moving position of 3 but it always manages to return it irrespective of the position of it in the array.

let myA = [12,3,8,5]
let myN = 4

function F4(A,N)
{
    if(N==1){
        return A[0]
    }
    if(F4(A,N-1) < A[N-1]){
        return F4(A,N-1)
    }
    return A[N-1]
}

console.log(F4(myA,myN))

CodePudding user response：

This is quite tricky to get an intuition for. It's also quite important that you learn the process for tackling this type of problem rather than simply be told the answer.

If we take a first view of the code with a few comments and named variables it looks like this:

let myA = [12,3,8,5];
let myN = myA.length;

function F4(A, N) {
    // if (once) there is only one element in the array "A", then it must be the minimum, do not recurse
    if (N === 1){
        return A[0]
    }

    const valueFromArrayLessLastEl = F4(A,N-1);     // Goes 'into' array
    const valueOfLastElement = A[N-1];

    console.log(valueFromArrayLessLastEl, valueOfLastElement);
    
    // note that the recursion happens before min(a, b) is evaluated so array is evaluated from the start
    if (valueFromArrayLessLastEl < valueOfLastElement) {
        return valueFromArrayLessLastEl;
    }

    return valueOfLastElement;
}

console.log(F4(myA, myN))

and produces

12 3 // recursed all the way down
3 8 // stepping back up with result from most inner/lowest recursion
3 5
3

but in order to gain insight it is vital that you approach the problem by considering the simplest cases and expand from there. What happens if we write the code for the cases of N = 1 and N = 2:

// trivially take N=1
function F1(A) {
    return A[0];
}

// take N=2
function F2(A) {
    const f1Val = F1(A);    // N-1 = 1
    const lastVal = A[1];

    // return the minimum of the first element and the 2nd or last element
    if (f1Val < lastVal) {
        return f1Val;
    }

    return lastVal;
}

Please note that the array is not being modified, I speak as though it is because the value of N is decremented on each recursion.

With myA = [12, 3, 8, 5] F1 will always return 12. F2 will compare this value 12 with 3, the nth-1 element's value, and return the minimum.

If you can build on this to work out what F3 would do then you can extrapolate from there.

Play around with this, reordering the values in myA, but crucially look at the output as you increase N from 1 to 4.

As a side note: by moving the recursive call F4(A,N-1) to a local constant I've prevented it being called twice with the same values.