Recursively Search in Array with a For Loop

Question

I know there are better ways to search an array, but I really want to understand how to return when the value is found in a recursive call. Logging when found isn't a problem, but I can't seem to make this return true when found.

The problem is basic. Fully search multi-dimensional array for a value and return true if found or false if not found, using a for loop and recursion. I've tried returning the recursive function and everything else I can think of, but nothing works fully.

function lookForKey( arr ){
    for ( let i = 0; i < arr.length; i++ ) {
        if( arr[i] == "key" ){
            console.log( "Key found.");
            return true;
        } else if( Array.isArray( arr[i] ) ){
            lookForKey( arr[i] );
        }
    }

    return false;
}

let arr = [
    ["foo", "bar"],
    ["foo", "bar", "key"]
];

console.log( lookForKey( arr ) );

I appreciate any insight on this!

Answer 1

Recursion is a functional heritage and so using it with functional style yields the best results. This means avoiding things like mutations, variable reassignments, and other side effects. for is a side effect and is the looping construct used in imperative style. Notice when we use functional style there's no reason to use for as recursion is the loop.

1. If the input arr is empty, there is nothing to search for. Return the base case, false
2. (induction) The input arr is not empty. If the first element arr[0] is an array, recursively search the element or recursively search the sub-problem, arr.slice(1)
3. (induction) The input arr is not empty and the first element is not an array. If the first element matches the query, q, return true, otherwise recursively search the sub-problem, arr.slice(1)

Below we write search using the inductive reasoning provided above -

function search (arr, q)
{ if (arr.length === 0)
    return false                                         // 1
  else if (Array.isArray(arr[0]))
    return search(arr[0], q) || search(arr.slice(1), q)  // 2
  else
    return arr[0] === q || search(arr.slice(1), q)       // 3
}

const input =
  [ ["foo", "bar"]
  , ["foo", "bar", "key"]
  ]

console.log(search(input, "key"))
console.log(search(input, "bar"))
console.log(search(input, "zzz"))

If we're splitting hairs, if, else, and return are also side effects. You can also write search as a pure expression -

const search = (arr, q) =>
  arr.length === 0
    ? false                                          // 1
: Array.isArray(arr[0])
    ? search(arr[0], q) || search(arr.slice(1), q)   // 2
: arr[0] === q || search(arr.slice(1), q)            // 3

const input =
  [ ["foo", "bar"]
  , ["foo", "bar", "key"]
  ]

console.log(search(input, "key"))
console.log(search(input, "bar"))
console.log(search(input, "zzz"))

And destructuring assignment makes things a little more declarative -

const none =
  Symbol("none")

const search = ([ v = none, ...more ], q) =>
  v === none
    ? false                             // 1
: Array.isArray(v)
    ? search(v, q) || search(more, q)   // 2
: v === q || search(more, q)            // 3

const input =
  [ ["foo", "bar"]
  , ["foo", "bar", "key"]
  ]

console.log(search(input, "key"))
console.log(search(input, "bar"))
console.log(search(input, "zzz"))

All variations of search above have the same output -

true
true
false

---

I sparked some controversy by making some comments about recursion and for loops not belonging to the same school of thought. First, here's what search could look like without recursion -

function search (arr, q)
{ const s = [arr]
  let v
  while(v = s.shift())
    if(Array.isArray(v))
      for (const _ of v)
        s.unshift(_)
    else if (v === q)
      return true
  return false
}

const input =
  [ ["foo", "bar"]
  , ["foo", "bar", "key"]
  ]

console.log(search(input, "key"))
console.log(search(input, "bar"))
console.log(search(input, "zzz"))

But that's not to say ideas cannot cross schools. Consider this variant that uses forEach with recursion and draws upon a call-with-current-continuation technique, callcc below -

const callcc = f =>
{ try { return f(value => { throw {callcc, value} }) }
  catch (e) { if (e.callcc) return e.value; else throw e }
}

function search (arr, q)
{ const loop = (t, exit) =>
    Array.isArray(t)
      ? t.forEach(v => loop(v, exit))
      : t === q && exit(t)
  return callcc(k => loop(arr, k))
}

const input =
  [ ["foo", "bar"]
  , ["foo", "bar", "key"]
  ]

console.log(search(input, "key"))
console.log(search(input, "bar"))
console.log(search(input, "zzz"))

Answer 2

The result comes as false because we are trying to return false from the function. While the for loop is running, the one way to break it when we get the desired result is to use break. And we can save the status of find in a variable called result which can be returned from the function lookForKey

function lookForKey( arr ) {
    var result = false;
    for ( let i = 0; i < arr.length; i++ ) {
        if( arr[i] == "key" ){
            result = true;
            break;
        } else if( Array.isArray( arr[i] ) ){
            result = lookForKey( arr[i] );
        }
    }

    return result;
}

In the above code, instead of returning false from the function, we are returning the result variable which contains the actual value of the search. We use break statement here to break out from for loop as soon as we get the desired result.

Answer 3

Asserting a found condition by returning true can be done in a single logical expression that will shortcut as soon as truth is undeniable.

function myFind( haystack, needle ){
    for ( let i = 0; i < haystack.length; i++ ) {
        if ( haystack[i] === needle 
             ||
             ( Array.isArray( haystack[i] ) 
               &&
               myFind( haystack[i], needle )
             )
           ) 
           return true; // return only when found

        // not found, check next array element
    }

    return false;  // not found as any element or in any element
}

let arr = [
    ["foo", "bar"],
    ["foo", "bar", "key"]
];

console.log( myFind( arr, "key" ) );
console.log( myFind( arr, "foo" ) );
console.log( myFind( arr, "xyzzy" ) );

Answer 4

function lookForKey( arr ){
    for ( let i = 0; i < arr.length; i++ ) {
        if( arr[i] == "key" ){
            console.log( "Key found.");
            return true;
        } else if( Array.isArray( arr[i] ) ){
            if (lookForKey(arr[i])) return true;
        }
    }

    return false;
}

let arr = [
    ["foo", "bar"],
    ["foo", "bar", "key"]
];

console.log( lookForKey( arr ) );

So two changes. First, you have to have the return on the recursive call. However, if the recursive call returns false, you don't want to return immediately from the caller. You want to continue the loop. So you can make that a conditional and only return true if the recursive call returns true.