0

Given

let doAsynchronousStuff = () => {
  return new Promise(resolve => {
    setTimeout(() => {
      resolve("abcdefg"[Math.floor(Math.random() * 7)])
    }, Math.PI * 1 + Math.random())
  })
  .then(data => console.log(data))
  .then(doAsynchronousStuff)
}

why is .then(doAsynchronousStuff) considered "pseudo-recursion"?

What is the difference between "recursion" and "pseudo-recursion"?

Context:

this isn't "real" recursion, because the event loop gets to unwind the stack before the .then callback gets called – Alnitak

Community
  • 1
  • 1
guest271314
  • 1
  • 15
  • 104
  • 177
  • 1
    I'm not sure the term "pseudo-recursion" is even meaningful; that code is not recursive at all. Yes, there's a reference to a function inside it's body code, but it's not a *call* to the function. – Pointy Nov 02 '16 at 22:42
  • @Pointy yeah, it does sound like something...not meaningful. I don't think it's a real term - not one I've heard of, at least - I'm guessing somebody used it as a shorthand to describe something that _kinda sorta_ looked like recursion from some angle, but it wasn't. – VLAZ Nov 02 '16 at 22:45
  • A function being called within it's own definition is recursive. I think this qualifies *"somewhat"*, at least if the promise resolves, as it calls the function, which calls the function, which.... etc. and wouldn't that be the definition of recursive. On the other hand it's not recursive because the `then` handler calls the function again, it's not directly called from within itself, so I guess *"pseudo recursive"* would be one way to look at it? Then again, in this case the promise is always resolved, so it's definitively recursive. – adeneo Nov 02 '16 at 22:46
  • @adeneo I agree. It is a function that when completes, via some chains and pulleys, gets kicked off again. So, yes, it's not "recursive" as it's not calling itself. Although the quote OP's has seems me it suggests "recursion" is used to mean that it "does stuff on the stack". – VLAZ Nov 02 '16 at 22:49
  • @adeneo thinking in terms of abstract algorithm expression, recursion is a function defined in terms of itself. That's not really what's going on here. There's nothing about that reference to the function that involves computing a result; it's just a procedural detail. – Pointy Nov 02 '16 at 22:52
  • That said I'm totally not a formalist and I don't like terminological pedanticism so please follow your bliss and call it whatever you like :) – Pointy Nov 02 '16 at 22:53
  • Because you could implement recursive algorithms with this pattern, for example fibonacci: let doAsynchronousStuff = (a, b) => { return new Promise(resolve => { setTimeout(() => { resolve(a+b) }, 10) }) .then(data => {console.log(data); return data}) .then(c => doAsynchronousStuff(b, c)) } – Max Vorobjev Nov 02 '16 at 22:56
  • @Pointy - I agree, *"recursion is the process a procedure goes through when one of the steps of the procedure involves invoking the procedure itself*" <- which is the definition of recursion, something one generally sees in programming when computing values with recursive function calls, but I tend to call almost any function that in some way or form calls itself, even in async callbacks, recursive, but per the definition, this wouldn't be recursive. – adeneo Nov 02 '16 at 22:56
  • @guest: It's just a plain old callback that gets executed at some point in the future. Think of it this way... if we have a `click` handler on an element, and when a click happens, it assigns that same function as the click handler of another element, would we call it recursion when someone clicks the second element? No, it's just a function being executed. –  Nov 02 '16 at 22:57
  • There appear to be different views on the topic. Can the comments be posted as Answers? Each of your input is valuable. – guest271314 Nov 02 '16 at 22:58
  • ...though it is a tempting term to use, especially when passing an anonymous function that invokes the original within. It *sort of* looks like recursion then... `function foo() { console.log("hi"); setTimeout(function() { console.log("bye"); foo(); }, 1000) } foo();` –  Nov 02 '16 at 23:01
  • @squint - it **is** just a plain callback, but the callback is the same function, so it runs over and over again, hence recursion, it recurs again? – adeneo Nov 02 '16 at 23:04
  • @adeneo: But we wouldn't call a function invocation in a loop recursion even though that runs over and over. In both cases, there's a separation between the original invocation and the next that would seem to take it out of the realm of actual recursion... but then Pointy's remark about pedantry is well taken. I wouldn't be too concerned if someone uses that word. –  Nov 02 '16 at 23:08
  • A function invocation in a loop is just iteration, to have recursion the function would have to be called within the function, which it does here, it's just that it's wrapped in an async callback and doesn't really recur to compute anything, i.e. the next iteration doesn't depend on the result from the previous iteration, which is generally what you'd call recursion in programming, regardless of async methods or stacks. – adeneo Nov 02 '16 at 23:11
  • @adeneo: Except that it isn't actually called within the function. In the question, it's passed elsewhere and then (possibly) called there. In my `setTimeout` example, it's call is *defined* in the anonymous function, but again actually called somewhere else. But I'd agree that "recursive" generally gets the point across that it is in some way self-referential, which is probably satisfactory in most situations. –  Nov 02 '16 at 23:18
  • @squint The asynchronous portions removed the pattern is recursion? Does this mean an asynchronous function cannot be recursive? – guest271314 Nov 02 '16 at 23:20
  • @squint - sure the function is passed to `then()`, which in turn calls the function again, but isn't that "indirect recursion" or "mutual recursion" or something like that? It can still be recursive even if it doesn't directly call itself. – adeneo Nov 02 '16 at 23:21
  • @guest271314: I'd go with Alnitak's view that it needs to be tied to the call stack. –  Nov 02 '16 at 23:23
  • @adeneo: I think qualifying terms like that are helpful. I'd even say asynchronously recursive if it wasn't such a mouthful. I think of "indirect recursion" as that which again continues to build the stack though by way of multiple functions. –  Nov 02 '16 at 23:24
  • On [wikipedia](https://en.wikipedia.org/wiki/Recursion_(computer_science)#Indirect_recursion) it says "indirect" and "mutual" is the same thing, I always thought those were different forms of recursion, but it's not. Both however covers calling a function that then calls the recursive function etc. but it doesn't really say anything about stacks or async. Then again, wikipedia is generally not where I usually look for accurate programming lingo ? – adeneo Nov 02 '16 at 23:30
  • @adeneo: I guess it still comes down to the distinction between a function calling itself, and a function passing a itself, which then gets called later. With higher-order functions combined with async execution giving us the ability to hand off execution that can happen at a later time, I think at least recognizing a distinction is good, irrespective of what we casually call it when we all know what we ultimately mean. So I'd call [this](https://jsfiddle.net/bbvzmx6t/) indirect recursion, and wouldn't sweat it too much if the code was reworked to be async. –  Nov 02 '16 at 23:39
  • See also http://www.ibm.com/developerworks/linux/library/l-recurs/index.html#N1035B – guest271314 Nov 04 '16 at 01:48

1 Answers1

2

The definition in my head for "recursive function" is that it is self-referential AND that the functional result depends upon the self referential invocation.

That means that the recursive invocation must be "synchronous". But that "synchronous" call need only be so relative to the invocation that depends on it, not relative to the system. In other words, the recursive function can run one call deeper on each turn of the run loop, and needn't build a deep stack, e.g.

// recursive but async
function factorial(x) {
    if (x === 0) { return 1; }
    return factorial(x-1).then(function(r) {
        return asyncMultiply(r, x);  // imagining that does r*x asynch
    });
}

Since something like this doesn't build the call stack the way we (me?) were classically taught, it wouldn't be crazy to qualify that as "pseudo".

danh
  • 62,181
  • 10
  • 95
  • 136
  • Is the function at Question recursive; implementing recursion? – guest271314 Nov 03 '16 at 01:31
  • @guest271314, I should have been clearer: no, it isn't a recursive function according to my suggested definition, but not because of the call stack. It's not a recursive function because it's not a function, it's a procedure with no return value. The self reference is necessary but nut sufficient. It's return value must *depend* on the value returned by the recursive call. – danh Nov 03 '16 at 05:37
  • _"I should have been clearer: no"_ Not certain what you mean? Recursive, recursion; yes, no? The return value is the `Promise` object, yes? – guest271314 Nov 03 '16 at 06:34
  • Yes - the return value is a promise that resolves to the factorial of the input param. No - the function proposed by the OP is not recursive by any definition I'm aware of. But it's failure to qualify is not a because it operates async. To demonstrate the distinction, I proposed a function that is async and is also recursive. – danh Nov 03 '16 at 14:11
  • _"No - the function proposed by the OP is not recursive by any definition I'm aware of"_ If not recursive or recursion, or tail recursion http://stackoverflow.com/questions/33923/what-is-tail-recursion/33928#33928 , what is the pattern at Question? – guest271314 Nov 03 '16 at 16:23
  • Is the pattern tail-call optimization http://www.ibm.com/developerworks/linux/library/l-recurs/index.html#N1035B ? – guest271314 Nov 03 '16 at 17:07
  • I cannot to classify the code given in the question as some type of recursive function, because it's not recursive. It's not even a function in the sense that it doesn't return anything. It's a procedure, a nonterminating procedure that happens to refer to itself. – danh Nov 03 '16 at 17:57
  • _"It's not even a function in the sense that it doesn't return anything."_ The function returns a `Promise` object. What is difference between a function and a procedure? – guest271314 Nov 03 '16 at 17:59