2

This Question is intended as a canonical Question/Answer for disambiguation as to the descriptive term "recursion", or "recursive". And to the extent applicable, "a non-terminating procedure that happens to refer to itself" and "repeated scheduling".

In JavaScript what are the definitions of and differences between

  1. "recursion";
  2. "a non-terminating procedure that happens to refer to itself"; and
  3. "repeated scheduling"

I often see the term "recursion" used when a function repeated calls itself, though what is the unambiguous definition of "recursion" in JavaScript?

Rarely have I viewed the terms "a non-terminating procedure that happens to refer to itself" or "repeated scheduling" used when describing the pattern of a function; frequently "recursive" or "recursion" is used to describe a pattern where within the body of the function call, a function call is made to the original function which began the process.

When is "recursion" not applicable to a particular function pattern; and what are the unambiguous definitions and distinctions between "recursion", "a non-terminating procedure that happens to refer to itself" and "repeated scheduling"?

guest271314
  • 1
  • 15
  • 104
  • 177

1 Answers1

2

Recursion

I often see the term "recursion" used when a function repeated calls itself, though what is the unambiguous definition of "recursion" in JavaScript?

That definition seems fine, but the function doesn't have to call itself directly to be recursive, it's execution just has to lead to it being called again. An example of recursion where the function doesn't directly call itself is: Calling A(); calls B(); which calls C(); which calls A(); again.

Repeated Scheduling

A function like this uses repeated scheduling:

function A ( foo ) {
  var bar;
  setTimeout( A, 0 );
  console.log( 'hello' );
}

It is not recursive because A isn't called repeatedly on the same call stack. When the current call stack is done (which means 'hello' will have been logged) and nothing else is ahead of calling A again in the event loop, A will be called. Aside from the difference between synchronous and asynchronous code, the important different here is that there is only ever one copy of foo and bar at a time, and the call stack isn't growing, hence there will be no memory or Maximum call stack size exceeded errors, which there would be for this version which uses recursion:

function A ( foo ) {
  var bar;
  A();
  console.log( 'hello' );
}

In that case 'hello' will never be printed since A calls itself before it gets to the logging statement.

A Non-Terminating Procedure that Refers to Itself

A non-terminating procedure is just an infinite loop. Referring to itself is somewhat meaningless:

function A ( ) {
    // Never terminates
    while ( true ) {
        // If A() is called here, or before
        // the loop you have infinite 
        // recursion and a stack size error
    }
    // If, instead, A() is called here,
    // you just have an infinite-loop,
    // since this statement is never reached
}
user229044
  • 232,980
  • 40
  • 330
  • 338
Paul
  • 139,544
  • 27
  • 275
  • 264
  • How is the third example different from first example, where stack size error is avoided, for example using `break` at some point within `while` statement, and `A()` is called following `while` loop? Is asynchronous calling of original function at some point in future still recursion? Or, is there a different evaluation when the function call includes asynchronous function calls before the original function is called again? – guest271314 Dec 22 '16 at 23:39
  • The third example isn't different from recursion if a break is added and `A();` is called after the loop. A stack size error would occur. – Paul Dec 22 '16 at 23:44
  • "Is asynchronous calling of original function at some point in future still recursion?" No (see the repeated scheduling example). "[I]s there a different evaluation when the function call includes asynchronous function calls before the original function is called again?" That's impossible, all asynchronous functions are executed after the call stack completes, you can't have synchronous code run after asynchronous code. – Paul Dec 22 '16 at 23:46
  • By "evaluation", meaning which category of the three mentioned at Question the pattern appropriately fits the corresponding description? For equivocal languages, one word or term can and often does have more than one definition. For example, which of the three would this pattern be `function doAsynchronousStuff() { return new Promise((resolve, reject) => { setTimeout(() => {resolve("test")}, 0) }) .then(console.log) .then(doAsynchronousStuff); }`? – guest271314 Dec 22 '16 at 23:48
  • 1
    @guest271314 That would be repeated scheduling, because `then` calls the function asynchronously. The only thing synchronous in `doAsynchronousStuff` is the return statement, which calls the Promise constructor, which calls the function passed into it, which calls setTimeout. Everything else is asynchronous. – Paul Dec 22 '16 at 23:52
  • If a function can `return` before calling itself again, is the function still considered "recursive"? For example, ignoring the logic, but focusing on the possibility of `if` or first `if..else` condition "evaluating" to `true`, `function isEven(n) { if (n == 0) return true; else if (n == 1) return false; else if (n < 0) return isEven(-n); else return isEven(n - 2); }`. If `if` condition evaluates to `true`, and `true` is `return`ed from `isEven` call; is, or should the function be considered "recursive"? – guest271314 Dec 22 '16 at 23:56
  • The function is recursive, and all recursive functions need some base case where they don't recurse, to avoid the maximum call stack size exceeded error and to return a final result. If you call it with like `isEven( 0 )`, it doesn't recurse, but the function itself is still considered recursive. – Paul Dec 23 '16 at 00:02
  • As long as there is some possible input or state which causes the function to lead to itself being called (synchronously) it is considered a recursive function. – Paul Dec 23 '16 at 00:03
  • Why is asynchronous procedure excluded from within the definition of recursion? That portion of distinction is where have, here, been not definitively certain as to why there is a difference between the two patterns. Can an asynchronous procedure, or a function which calls an asynchronous process, then calls itself, ever be "recursive"? Or, is that pattern only ever considered "repeated scheduling", or "a non-terminating procedure that happens to refer to itself"? – guest271314 Dec 23 '16 at 00:06
  • 1
    @guest271314 It just depends on whether the function returns before it is called again. `isEven` can call itself before it returns (EG. `isEven(2)` calls `isEven(0)` before returning), so it is recursive. `doAsynchronousStuff` returns a Promise immediately, so it has already returned and is not on the call stack anymore when it is called again asynchronously. – Paul Dec 23 '16 at 00:16
  • The measure of whether a function is recursive or not depends directly on the whether the function is placed within the call stack by the function itself? Not whether the function returns an asynchronous result? Or, are all asynchronous functions not placed onto the call stack? Or are asynchronous functions called then removed from the call stack? Or is the process different from all of the above? If an asynchronous function includes a condition for a base case, can it too be recursive? – guest271314 Dec 23 '16 at 00:20
  • 1
    "The measure of whether a function is recursive or not depends directly on the whether the function is placed within the call stack by the function itself?" Yes. "Not whether the function returns an asynchronous result?" Correct. "Or, are all asynchronous functions not placed onto the call stack? Or are asynchronous functions called then removed from the call stack?" They are not placed on the existing call stack, but they will be the start of a new call stack at some point later, after the current call stack finished and they are next in the event loop's queue. – Paul Dec 23 '16 at 00:27
  • The first example uses the setTimout function to terminate the loop. The third example has nothing to stop. So it will run until it blows the stack. When you create a while statement and set it to true without anything to alter it then it will always be true. It one of those I am because I am things. If you include the A function alter the while loop or before it the function will still be Non-Terminating. It will either get stuck in the while or in calling itself. The only place you could place a break to stop the madness would be before the while or before recursive function calling itself. – andre mcgruder Dec 23 '16 at 02:25