Recursive function with timeout to prevent stack call exceeded

Question

I am trying to find any and all images an any object of any depth with a recursive function, but as expected it will give a Maximum call stack size exceeded error in some applications. The solution here said to wrap the recursive function in a setTimeout but then it appears the the function doesn't work an anymore.

const resultsReg = []
const resultsTimeout = []
const obj = {
    key : {
        foo: 'bar.jpg'
  }
}

function findImages(object, results) {
  for (var key in object) {
    if (typeof object[key] === 'string') {
      if (object[key].match(/\.(jpg)$/i) && !results.includes(object[key]) && results.length < 9) results.push(object[key]);
    }
    else if (typeof object[key] === 'object') {
      findImages(object[key], results); // this works, but in some applications will give Maximum call stack size exceeded error
    }
  }
}

function findImagesTimeout(object, results) {
  for (var key in object) {
    if (typeof object[key] === 'string') {
      if (object[key].match(/\.(jpg)$/i) && !results.includes(object[key]) && results.length < 9) results.push(object[key]);
    }
    else if (typeof object[key] === 'object') {
      setTimeout(function() {
        findImagesTimeout(object[key], results) // this fails
      }, 0)
    }
  }
}

findImages(obj, resultsReg)
findImagesTimeout(obj, resultsTimeout)
console.log(resultsReg)
console.log(resultsTimeout)

output:

[ 'bar.jpg' ]
[]

Am I doing something wrong?

It is impossible to get the value like that with asynchronous. Use promises — epascarello, May 11 '17 at 13:18
Also, could you clarify what you mean by 'some applications'? — Stumblor, May 11 '17 at 13:20
By introducing a timeout, you make the code asynchronous. You'll have to work with callbacks - or better yet, promises - to "get back" the future result — Bergi, May 11 '17 at 13:30
I use this function when trying to find images in RSS feeds. The depth of the object varies widely from feed to feed. I see now that it does make it asynchronous - but to work with callbacks/promises, how would I be able to check when the function is 'finished' with the object? For arrays I can check match its `.length` but what about objects? — platizin, May 11 '17 at 13:52

Karim · Answer 1 · 2017-05-11T13:34:45.727

that trick won't work because you're inside a for loop so the parser wont be able to clear the stack and the exception will most likely be triggered.

you could keep trace of the functions to call inside a variable and call them when the loop finish.

something like this

function findImagesTimeout(object, results) {
  var fn = []; //keep trace of the functions to call
  for (var key in object) {
    if (typeof object[key] === 'string') {
      if (object[key].match(/\.(jpg)$/i) && !results.includes(object[key]) 
      && results.length < 9) 
       results.push(object[key]);
    }
    else if (typeof object[key] === 'object') {
      fn.push(function(key) {
        return function(){
         findImagesTimeout(object[key], results)
        }
      }(key));
    }
  }

  setTimeout(function(){
    fn.forEach(function(singleFn){
      singleFn();
    });
  }, 0);

 }
}

score 0 · Answer 2 · answered May 11 '17 at 13:23

I think your timeout is useless in this case.

https://jsfiddle.net/f9c185p2/

function findImagesTimeout(object, results) {
  for (var key in object) {
    if (typeof object[key] === 'string') {
      if (object[key].match(/\.(jpg)$/i) && !results.includes(object[key]) && results.length < 9) results.push(object[key]);
    }
    else if (typeof object[key] === 'object') {
      findImagesTimeout(object[key], results);
    }
  }
}

score 0 · Accepted Answer · answered May 11 '17 at 14:33

To avoid the Maximum call stack size exceeded error you could use a trampoline function, which will prevent the stack from overflowing. Instead of directly executing the recursive call adding another stack frame, you basically return a wrapper function which will handle the execution.

Here is an example.

const resultsReg = []
const obj = {
  key : {
    foo: 'foo.jpg',
    key: {
      bar: 'bar.jpg',
      key: {
        baz: 'baz.jpg'
      },
      point: {
       x: 32,
        y: 64
      }
    },
    url: 'google.com',
  }
}

function trampoline (func, obj, reg) {
  var value = func(obj, reg);
  while(typeof value === "function") {
    value = value();
  }
  return value;
}

function findImages (obj, reg) {
  for (var key in obj) {
    if (Object.prototype.toString.call(obj[key]) === '[object Object]') {
      return function () {
        return findImages(obj[key], reg);
      }
    } else {
      if (obj[key].match(reg)) {
        // Here you can start to push.
        resultsReg.push(obj[key])
      }
    }
  }
}

trampoline(findImages, obj, /\.(jpg)$/);

console.log(resultsReg)

This is a bit late, but by returning the function in the for loop, it won't iterate over anything else once it reaches the first object (`obj[key]`) in that particular object. I can't seem to figure out how to do trampolining in this case without prematurely stopping the loop — platizin, Jun 24 '17 at 23:27

Recursive function with timeout to prevent stack call exceeded

3 Answers3