Promise with recursion

问题:

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.

回答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.

回答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 ]

回答3:

Try not to use shared mutable state in your functions (especially when they are asynchronous). You are using window.i but anything can change that value, this is not needed because the i value is only used in your function as a counter:

const later = (milliseconds,value) =>
  new Promise(
    resolve=>
      setTimeout(
        ()=>resolve(value),
        milliseconds
      )
  );

const countTo = toWhat => {
  const recur = counter =>
    later(1000,counter)
    .then(
      i=>{
        console.log(`i is now: ${i}`);
        return (i<toWhat)
          ? recur(i+1)
          : i;
      }
    )
  return recur(1);
}

countTo(10)
.then(
  i=>console.log(`i ended up at: ${i}`)
);