Promise with recursion

Question

I've taken a look at a few questions on recursion in promises and am confused on how to implement them properly:

• Recursive Promise in javascript
• AngularJS, promise with recursive function
• Chaining Promises recursively
• Javascript Recursive Promise

I put together a simple example (see below) - this is just an example so I can understand how to make recursion with promises work and not a representation of the code in which I'm working.

Net-net, I'd like the promise to resolve, but according to the output on node, it doesn't resolve. Any insight into how to make this resolve?

var i = 0;

var countToTen = function() { 
    return new Promise(function(resolve, reject) {
        if (i < 10) {
            i++;
            console.log("i is now: " + i);
            return countToTen();
        }
        else {
            resolve(i);
        }
    });
}

countToTen().then(console.log("i ended up at: " + i));

And the output on the console:

> countToTen().then(console.log("i ended up at: " + i));
i is now: 1
i is now: 2
i is now: 3
i is now: 4
i is now: 5
i is now: 6
i is now: 7
i is now: 8
i is now: 9
i is now: 10
i ended up at: 10
Promise { <pending> }

The promise never resolves.

Answer 1

If you look at your code as long as i is less than 10 you are recursing and never resolving the promise. You eventually resolve a promise. but it is not the promise the initial caller gets.

You need to resolve with the promise returned by the recursion. How the system works if you resolve with a promise it will still not resolve until also the value is resolved:

let i = 0;
const countToTen = () => new Promise((resolve, reject) => {
    if (i < 10) {
      i++;
      console.log("i is now: " + i);
      resolve(countToTen());
    } else {
      resolve(i);
    }
  });

countToTen().then(() => console.log("i ended up at: " + i));

There was an error in the last part as well. You didn't provide a function to then so if you would have done something that actually would have waited you would have got the "i ended up at: 0" first.

Answer 2

it would be better if you made i a parameter of the function instead of relying upon external state

const countToTen = (i = 0) =>
  new Promise ((resolve, _) =>
    i < 10
      ? (console.log (i), resolve (countToTen (i + 1)))
      : resolve (i))
      
      
countToTen () .then (console.log, console.error)
// 0 1 2 3 4 5 6 7 8 9 10

And even better if you made 10 a parameter too

const countTo = (to, from = 0) =>
  new Promise ((resolve, _) =>
    from < to
      ? (console.log (from), resolve (countTo (to, from + 1)))
      : resolve (from))

countTo (7, 2) .then (console.log, console.error)
// 2 3 4 5 6 7

A more generic approach is a reverse fold - or unfold

const unfold = (f, init) =>
  f ( (x, acc) => [ x, ...unfold (f, acc) ]
    , () => []
    , init
    )

const countTo = (to, from = 0) =>
  unfold
    ( (next, done, acc) =>
        acc <= to
          ? next (acc, acc + 1)
          : done ()
    , from
    )

console.log (countTo (10))
// [ 0, 1, 2, 3, 4, 5, 6,  7, 8, 9, 10 ]

console.log (countTo (7, 2))
// [ 2, 3, 4, 5, 6, 7 ]

But you want a asynchronous unfold, asyncUnfold. Now the user-supplied function f can be async and we get a Promise of all collected values

const asyncUnfold = async (f, init) =>
  f ( async (x, acc) => [ x, ...await asyncUnfold (f, acc) ]
    , async () => []
    , init
    )

const delay = (x, ms = 50) =>
  new Promise (r => setTimeout (r, ms, x))

const countTo = (to, from = 0) =>
  asyncUnfold
    ( async (next, done, acc) =>
        acc <= to
          ? next (await delay (acc), await delay (acc + 1))
          : done ()
    , from
    )

countTo (10) .then (console.log, console.error)
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

countTo (7, 2) .then (console.log, console.error)
// [ 2, 3, 4, 5, 6, 7 ]

Here's a more practical example where we have a database of records and we wish to perform a recursive look-up, or something...

• db.getChildren accepts a node id and returns only the node's immediate children

• traverse accepts a node id and it recursively fetches all descendant children (in depth-first order)

const data =
  { 0 : [ 1, 2, 3 ]
  , 1 : [ 11, 12, 13 ]
  , 2 : [ 21, 22, 23 ]
  , 3 : [ 31, 32, 33 ]
  , 11 : [ 111, 112, 113 ]
  , 33 : [ 333 ]
  , 333 : [ 3333 ]
  }

const db =
  { getChildren : (id) =>
      delay (data [id] || [])
  }

const Empty =
  Symbol ()

const traverse = (id) =>
  asyncUnfold
    ( async (next, done, [ id = Empty, ...rest ]) =>
        id === Empty
          ? done ()
          : next (id, [ ...await db.getChildren (id), ...rest ])
    , [ id ]
    )

traverse (0) .then (console.log, console.error)
// [ 0, 1, 11, 111, 112, 113, 12, 13, 2, 21, 22, 23, 3, 31, 32, 33, 333, 3333 ]