1

So I have a sample code for a function the goes through an array and all of it's sub-arrays by recursion, and counts the number of matching found strings.

sample array:

const array = [
    'something',
    'something',
    [
        'something',
        'something'
    ],
    'something',
    [
        'something',
        [
            'something',
            'something'
        ],
        'something',
        [
            [
                'something',
                'something',
                [
                    'anything'
                ]
            ],
            'something',
        ],
        [
            'something',
            [
                'something',
                'something',
                'something',
                [
                    'anything',
                    'something',
                    [
                        'something',
                        'anything'
                    ]
                ]
            ]
        ]
    ],
    'anything'
];

My function can go through this array and count the number of "something"'s in it.

This code works well:

let somethingsFound = 0;
const searchArrays = (array, stringMatch) => {
    for(let i=0;i<array.length;i++){
        const item = array[i];
        if((typeof item) === 'string'){
            (item === stringMatch) ? somethingsFound++ : undefined;
        } else if ((typeof item) === 'object'){
            searchArrays(item, stringMatch);
        }
    }
}

searchArrays(array, 'something');
console.log(`Found ${somethingsFound} somethings`);

console output:

>Found 18 somethings

However Here is the part I don't understand and need some explanation about. If i remove the let declaration on the forloop variable i and just implicitly declare it i=0;<array.length;i++ then my function goes into infinite recursion. I checked it by putting a console.log("running search) statement and saw that.

What does the let do exactly in this situation? I have tried reading about it but couldn't quite understand what's going on, and how exactly the recursion and forloop interact.

here's the failing block of code just in case, all that differs is that let declartion:

let somethingsFound = 0;
const searchArrays = (array, stringMatch) => {
    for(i=0;i<array.length;i++){
        const item = array[i];
        if((typeof item) === 'string'){
            (item === stringMatch) ? somethingsFound++ : undefined;
        } else if ((typeof item) === 'object'){
            searchArrays(item, stringMatch);
        }
    }
}

searchArrays(array, 'something');
console.log(`Found ${somethingsFound} somethings`);

Thanks! CodeAt30

2
  • Inner function always have access to variable declared inside the parent function its called Closures!. So your resetting value of i every time and hence infinite looping
    – deven98602
    Feb 19, 2018 at 15:49
  • 1
    @deven98602: While that's true, it's irrelevant to the OP's code, which doesn't have nested functions. Feb 19, 2018 at 15:51

3 Answers 3

4

...and just implicitly declare it i=0;

That's not a declaration, it's just creating an implicit global*. Since it's a global, it's shared by all of the calls to searchArrays, so your outer calls are ending prematurely (because i has been incremented by your inner calls).

Example:

function withDeclaration(recurse) {
  for (let i = 0; i < 3; ++i) {
    console.log((recurse ? "Outer " : "Inner ") + i);
    if (recurse) {
      withDeclaration(false);
    }
  }
}
function withoutDeclaration(recurse) {
  for (i = 0; i < 3; ++i) {
    console.log((recurse ? "Outer " : "Inner ") + i);
    if (recurse) {
      withoutDeclaration(false);
    }
  }
}

console.log("With declaration:");
withDeclaration(true);
console.log("Without declaration:");
withoutDeclaration(true);
.as-console-wrapper {
  max-height: 100% !important;
}

The moral of the story: Never rely on implicit globals. Declare your variables, in the innermost scope in which you need them. Use "use strict" to make implicit global creation an error.


* (that's a post on my anemic little blog)

2

When you use the "implicitly declared" variable, you will only have one such variable, independent of where you are in the recursion tree. It will be one global variable.

That will effectively destroy the logic of your algorithm, as the deepest recursion level will move the value of i beyond the array length, and then when you backtrack the loop at the previous recursion level will suddenly jump to that value of i, probably skipping several valid array entries it should have dealt with.

Always declare variables.

2

TJ and Trincot do a good job of fixing your program – I'm going to try to fix your thinking...

recursion is a functional heritage

Recursion is a concept that comes from functional style. Mixing it with imperative style is a source of much pain and confusion for new programmers.

To design a recursive function, we identify the base and inductive case(s)

  • base case – the first value of the input is Empty - if the input is empty, there are obviously no matches, therefore return 0
  • inductive case 1first is not empty, but it is an Array – recur on first plus recur on the rest of the values
  • inductive case 2 - first is not empty and not an array, therefore it is a plain value – if first matches match, return 1 for the match plus the result of recurring on the rest of the values
  • inductive case 3 - first is not empty, not an array, nor does it match match – recur on the rest of values

As a result of this implementation, all pain and suffering are removed from the program. We do not concern ourselves with local state variables, variable reassignment, array iterators, incrementing iterators, or other side effects like for

For brevity's sake, I replaced 'something' and 'anything' in your data with 'A' and 'B' respectively.

const Empty =
  Symbol ()
  
const searchArrays = (match, [ first = Empty, ...rest ]) =>
{
  /* no value */
  if (first === Empty)
    return 0
    
  /* value is NOT empty */
  else if (Array.isArray (first))
    return searchArrays (match, first) + searchArrays (match, rest)
  
  /* value is NOT array */
  else if (first === match)
    return 1 + searchArrays (match, rest)
  
  /* value is NOT match */
  else 
    return searchArrays (match, rest)
}

const data =
  ['A','A',['A','A'],'A',['A',['A','A'],'A',[['A','A',['B']],'A',],['A',['A','A','A',['B','A',['A','B']]]]],'B']

console.log (searchArrays ('A', data)) // 18
console.log (searchArrays ('B', data)) // 4
console.log (searchArrays ('C', data)) // 0

with functional style

Or encode searchArrays as a pure functional expression – this program is the same but exchanges the imperative-style if/else if/else and return statement syntaxes for ternary expressions

const Empty =
  Symbol ()
  
const searchArrays = (match, [ first = Empty, ...rest ]) =>
  first === Empty
    ? 0
    : Array.isArray (first)
      ? searchArrays (match, first) + searchArrays (match, rest)
      : first === match
        ? 1 + searchArrays (match, rest)
        : searchArrays (match, rest)

const data =
  ['A','A',['A','A'],'A',['A',['A','A'],'A',[['A','A',['B']],'A',],['A',['A','A','A',['B','A',['A','B']]]]],'B']

console.log (searchArrays ('A', data)) // 18
console.log (searchArrays ('B', data)) // 4
console.log (searchArrays ('C', data)) // 0

without magic

Above, we use a rest parameter to destructure the input array. If this is confusing to you, it will help to see it in a simplified example. Note Empty is used so that our function can identify when to stop.

const Empty =
  Symbol ()

const sum = ([ first = Empty, ...rest]) =>
  first === Empty
    ? 0
    : first + sum (rest)

console.log (sum ([ 1, 2, 3, 4 ])) // 10
console.log (sum ([]))             // 0

This is a high-level feature included in newer versions of JavaScript, but we don't have to use it if it makes us uncomfortable. Below, we rewrite sum without the fanciful destructuring syntaxes

const isEmpty = (xs = []) =>
  xs.length === 0
  
const first = (xs = []) =>
  xs [0]
  
const rest = (xs = []) =>
  xs.slice (1)

const sum = (values = []) =>
  isEmpty (values)
    ? 0
    : first (values) + sum (rest (values))
    
console.log (sum ([ 1, 2, 3, 4 ])) // 10
console.log (sum ([]))             // 0

We can take our isEmpty, first, and rest functions and reimplement searchArrays now – notice the similarities; changes in bold

const searchArrays = (match, values = []) =>
  isEmpty (values)
    ? 0
    : Array.isArray (first (values))
      ? searchArrays (match, first (values)) + searchArrays (match, rest (values))
      : first (values) === match
        ? 1 + searchArrays (match, rest (values))
        : searchArrays (match, rest (values))

Expand the code snippet to see that it works the same

const isEmpty = (xs = []) =>
  xs.length === 0
  
const first = (xs = []) =>
  xs [0]
  
const rest = (xs = []) =>
  xs.slice (1)
  
const searchArrays = (match, values = []) =>
  isEmpty (values)
    ? 0
    : Array.isArray (first (values))
      ? searchArrays (match, first (values)) + searchArrays (match, rest (values))
      : first (values) === match
        ? 1 + searchArrays (match, rest (values))
        : searchArrays (match, rest (values))

const data =
  ['A','A',['A','A'],'A',['A',['A','A'],'A',[['A','A',['B']],'A',],['A',['A','A','A',['B','A',['A','B']]]]],'B']

console.log (searchArrays ('A', data)) // 18
console.log (searchArrays ('B', data)) // 4
console.log (searchArrays ('C', data)) // 0

with powerful abstraction

As programmers, "traverse a data structure and do an operation on each element" is a common thing we need to do. Identifying these patterns and abstracting them into generic, reusable functions is at the core of higher-level thinking, which unlocks the ability to write higher-level programs like this

const searchArrays = (match, values = []) =>
  deepFold ( (count, x) => x === match ? count + 1 : count
           , 0
           , values
           )

This skill does not come automatically but there are techniques that can help you achieve higher-level thinking. In this answer I aim to give the reader a little insight. If this sort of thing interests you, I encourage you to take a look ^_^

recursion caution

JavaScript does not yet support tail call elimination which means extra precaution needs to be taken when writing recursive functions. For a code example that follows your program closely, see this answer.

3
  • Wow this answer was amazing. I had to do a lot of term catching up, I didn't know what Symbol(), ..., ..rest were and then read through your explanations and examples again. Thanks a lot for this it was quite a learning experience! There's one thing i didn't understand syntax-wise: in const searchArrays = (match, [ first = Empty, ...rest ]) is the first=Empty necessary or is just for clarity's sake? could `const searchArrays = (match, [first, ...rest ]) work the same? Thanks again this was wonderful!
    – CodeAt30
    Feb 20, 2018 at 11:55
  • Also I will look into your posts about the powerful abstraction further on since that was above my level for now i think.
    – CodeAt30
    Feb 20, 2018 at 11:56
  • @CodeAt30 delighted to help. If you change to [first, ...rest] you just have to change first === Empty to first === undefined - which was my comment about the explicit vs implicit stopping value ^_^
    – Mulan
    Feb 20, 2018 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.