Recursive version of find()

Question

What i'm trying to do is make a recursive version of find, which takes an array and a test function and returns first element of an array, that passes the test. Lets look at the example:

function isEven(num) { return(num%2 == 0); }
var arr = [1, 3, 5, 4, 2];

function findRecursive(arr, func) {
    var p = arr.shift();
    if (func(p) == true)
        return p;
    else 
        findRecursive(arr, func);
}

findRecursive(arr, isEven);

By some reason i'm getting undefined. But if i change shift to pop on line 5, it correctly returns 2. What causes th problem?

you forgot to return from `findRecursive` . For your `else` clause you should `return findRecursive(arr, func);` — Prasanna, Sep 22 '17 at 18:44

Nina Scholz · Accepted Answer · 2017-09-22T18:51:48.137

2

You need to return the value of the recursive call, otherwise you return undefined, the standard return value of a function in Javascript.

} else {
    return findRecursive(arr, func);
    // ^^^
}

You may insert a check for the length of the array, if there is no more element to check. Then you could return undefined intentionally.

function isEven(num) { return num % 2 === 0; }

function findRight(array, fn) {
    if (!array.length) {
        return;
    }

    var p = array.pop();
    return fn(p) ? p : findRight(array, fn);
}

console.log(findRight([1, 3, 5, 4, 2], isEven)); // 2
console.log(findRight([1, 3, 5], isEven));       // undefined

edited Sep 22 '17 at 18:51

answered Sep 22 '17 at 18:34

Nina Scholz

376,160
25
347
392

Please put a test for if there are no even values. – Matt Sep 22 '17 at 18:45
@Matt, nice catch :-) – Nina Scholz Sep 22 '17 at 18:52

Mulan · Answer 2 · 2017-09-23T18:06:42.957

Recursion is a looping mechanism that was born in the context of functional programming; taking it out of that context only permits a crude understanding of how recursion is meant to be used

Recursion, when used with other functional programming practices like persistent (immutable) data types and pure functions, can be expressed beautifully as a pure expression

const find = (f, [x,...xs]) =>
  x === undefined
    ? x
    : f (x)
      ? x
      : find (f, xs)

const isEven = x =>
  (x & 1) === 0
      
console.log (find (isEven, [1, 3, 5, 4, 2])) // 4
console.log (find (isEven, [1, 3, 5, 7, 9])) // undefined

Be careful with recursion in JavaScript, tho – use a stack-safe looping mechanism to avoid blowing the stack on a large array

const recur = (...values) =>
  ({ type: recur, values })
  
const loop = f =>
  {
    let acc = f ()
    while (acc && acc.type === recur)
      acc = f (...acc.values)
    return acc
  }
  
const find = (f, xs) =>
  loop ((i = 0) =>
    i === xs.length
      ? undefined
      : f (xs [i])
        ? xs [i]
        : recur (i + 1))

const isEven = x =>
  (x & 1) === 0

// [ 1, 2, 3, 4, ... 20000 ]
const numbers =
  Array.from (Array (2e4), (x,n) => n + 1)
  
console.log (find (isEven, numbers))     // 2

// this would have blown the stack using the first version of `find`
// but it works just fine here, thanks to loop/recur
console.log (find (x => x < 0, numbers)) // undefined

Your own `recur`, huh. Take that, Rich Hickey! JS is some kind of heaven for a DIY kind of programmer. :) — Will Ness, Sep 23 '17 at 17:31
@WillNess overcoming some of JavaScript's "shortcomings" has taught me so much about programming ^_^ — Mulan, Sep 23 '17 at 17:33

Recursive version of find()

2 Answers2