I am struggling with recursive functions. Though after some research and reading I is getting easier. But this problem is tripping me up. I could not find answer from anywhere

Write a recursive function called someRecursive which accepts an array and a callback. The function returns true if a single value in the array returns true when passed to the callback. Otherwise it returns false.

*// SAMPLE INPUT / OUTPUT
// const isOdd = val => val % 2 !== 0;

// someRecursive([1,2,3,4], isOdd) // true
// someRecursive([4,6,8,9], isOdd) // true
// someRecursive([4,6,8], isOdd) // false
// someRecursive([4,6,8], val => val > 10); // false*

function someRecursive(array, callback) {
    if (array.length === 0) return false;
    if (callback(array[0])) return true;
    return someRecursive(array.slice(1),callback);
}

This one line I do not understand : if (callback(array[0])) return true; Why "callback" needs arr[0] to return true, what's going on?

CodePudding user response：

The idea here is just to use recursion instead of a for loop (very normal programming style in scheme. Less usual in javascript. But, well, I take it is a school exercise on recursion).

Your function someRecursive goal seems to be to return true iff callbak(elt) is true for one of the elements of a list.

So someRecursive([1,2,3,4], isOdd) is true iff isOdd(1) or isOdd(2), or isOdd(3) or isOdd(4) is true. Which is the case.

Likewise for someRecursive([4,6,8,9], isOdd)

But someRecursive([4,6,8], isOdd) return false since isOdd(4) isOdd(6) and isOdd(8) are all false

Likewise someRecursive([4,6,7], val=>val>10) because the function val=>val>10 (a function that returns true iff it is called with a value > 10) returns false for 4, 6, and 7.

You could have coded that with a for loop

function someIterative(array, callback):
    for(let e of array){
        if(callback(e)) return true;
    }
    return false;
}

Note that for an empty array, answer is false (no element of the array returns true when used as a parameter to callback, since there isn't any element of the array).

So, the first thing you have to understand is the role of the callback. Which has nothing to do with recursion.

Now, recursion uses a different way to test callback(e) for all e in array. The logic is to test callback(e) on the first element. And then on the others.

Hence the implementation you've shown

// callback is the same as in the iterative version. Just what we want to test on all elements
// array is the yet untested list of elements (for the first call, it is the whole list, and then, for the subsequent recursive call, it is the list of elments but those we have already tested)
function someRecursive(array, callback){
   // If array in empty, there is no more hope to find any elements e for which callback(e) is true is array
   if(array.length==0) return false;
   // if we are still here, array is a non-empty list of elements we want to test. Let's start with the first
   if(callback(array[0])) return true; // if callback is true for the first, no need to continue, we know the final answer is true
   // If we are still here, callback(e) is false when e is the first element of the array
   // Let's test also the other. The others array.slice(1). List of all elements but the first. 
   // We could iterate on those. But no need to. We already have a function that iterate through a list and test if any callback(e) of this list is true. It is the someRecursive function we are writing
   return someRecursive(array.slice(1), callback);
}

What you need to do now is trace what this function would return for different examples.

For example, someRecursive([1,2,3,4], isOdd) would do

• [1,2,3,4].length==0 is false, so 1st line does nothing
• isOdd([1,2,3,4][0]) = isOdd(1) is true. So 2nd line return true. End of comptutation

someRecursive([4,5,6,7], isOdd)

• [4,5,6,7].length is not 0 ⇒ 1st line does nothing
• isOdd(4) is false, so 2nd line does nothing
• so, value of someRecursive([4,5,6,7], isOdd) is someRecursive([4,5,6,7].slice(1), isOdd), so is someRecursive([5,6,7], isOdd)
  • Recursion occurs to compute someRecursive([5,6,7], isOdd)
    • [5,6,7].length is not 0, so 1st line does nothin
    • callback(5) is true (5 is odd), so 2nd line returns true
    • so value of someRecursive([5,6,7], isOdd) is true
  • so value of someRecursive([4,5,6,7], is Odd) is true
• end of computation

CodePudding user response：

the "callback(array[0])" actually means a call "isOdd(array[0])", and that function returns true if the first element of the array is odd. Then you are done. If it does not return true, then the someRecursive() is called with a new array with the first element of the original array removed, and the process repeats... so the isOdd will be called for the element 0 of the array, then element 1 of the array... etc. until the array length shrinks to 0.

The wording of the problem is bit bizzare.

CodePudding user response：

I like the answer from chrslg. Think of this as merely a supplement to it.

One way at looking at this question, and at many questions which involve recursion and arrays, is to think of a different way to look at arrays. In this view,

An array is either

• empty

or

• an element followed by an array

Thus the array [8, 6, 7, 5, 3, 0, 9] is not empty. It is the element 8 followed by the array [6, 7, 5, 3, 0, 9], which itself is the element 6 followed by the array [7, 5, 3, 0, 9], ... and [0, 9] is the element 0 followed by the array [9], which is itself the element 9 followed by the array []. Now we've reached the empty array, and we can see our array as something like:

[8; [6; [7; [5; [3; [0; [9; []]]]]]]]

This is not how arrays are actually implemented in JS. There are many libraries and entire languages where this is the norm, and we can model this inside JavaScript by using array [0] and array .slice (1), once we've determined that the array is not empty (array .length !== 0), we know that we can use array [0], and array .slice (1) as our two parts.

This view makes it easier to write many recursive algorithms over arrays. In this model, someRecursive takes an array and a predicate function and tests whether the predicate returns true for some element in the array by checking the two cases, given our predicate, pred:

• If the array is empty, we return false
• If the array is an element, element, followed by the rest of the array, rest, then we return true if pred (element) is true. Otherwise we return the result somRecursive (rest, pred).

This is expressed directly in the code you shared

function someRecursive(array, callback) {
    if (array.length === 0) return false;
    if (callback(array[0])) return true;
    return someRecursive(array.slice(1),callback);
}

I would prefer, through to write it slightly differently, more directly exposing that model:

const someRecursive = (xs, pred) => 
  xs .length == 0 
    ? false
    : pred (xs [0]) || someRecursive (xs .slice (1), pred)

This expresses the algorithm fairly explicitly in that model of arrays.

I often write this slightly differently:

const None = Symbol();

const someRecursive = ([x = None, ...xs], pred) => 
  x == None 
    ? false
    : pred (x) || someRecursive (xs, pred)

Here we break the list explicitly into a first element, x, and the rest, xs. If the first element is our None signal, then we know that the array is empty.

It also makes parallels very clear. If we want to write everyRecursive, it should look quite familiar:

const everyRecursive = ([x = None, ...xs], pred) => 
  x == None 
    ? true
    : pred (x) && everyRecursive (xs, pred)

There are many reasons to use recursion. It can express ideas more directly. It often leads to cleaner code. But there are some real downsides in JS. It is usually less efficient, sometimes substantially so. And there are recursion depth limits. If you try to use the above code on arrays longer than perhaps 20,000 entries, it will probably fail, even if we put all recursive calls in tail-call position.