How to Handle Closure Recursivity

Javascript closures and recursion

A closure is simply a function or procedure that "closes over" an environment (it's body). In your code, init, displayName, and factorial are all closures. You use JavaScript function keyword (or now we have => arrow functions in ES6) when you want to create a closure.

Recursion is the effect of a procedure repeating itself

I've been reading a new book and it talks about some relevant topics. I thought I'd just share some notes here in case you were interested.

Here's a recursive function for calculating factorials. It does the same thing as yours but in a very different way. Let's see!

function factorial(x) {
  if (x < 0) throw Error("Cannot calculate factorial of a negative number");
  function iter(i, fact) {
    return i === 0 ? fact : iter(i-1, i*fact);
  }
  return iter(x, 1);
}

factorial(6); // 720

Compare it to the one you defined above ^.^. Notice that even though it's recursive, it doesn't call itself (factorial) again. This uses a linear iterative process that consumes linear space and time. The evaluation of the function looks something like this

factorial(6);
  iter(6, 1);
  iter(5, 6*1); 
  iter(4, 5*6);
  iter(3, 4*30);
  iter(2, 3*120);
  iter(1, 2*360);
  iter(0, 1*720);
// => 720

Compare that to the process of your function. Here's what yours would look like

factorial(6);
(6 * factorial(5));
(6 * (5 * factorial(4)));
(6 * (5 * (4 * factorial(3))));
(6 * (5 * (4 * (3 * factorial(2)))));
(6 * (5 * (4 * (3 * (2 * factorial(1))))));
(6 * (5 * (4 * (3 * (2 * 1)))));
// => 720

Notice that as n increases, n! adds another stack call. This is a linear recursive process. For large values of n, this method uses significantly more space to calculate the same result.

Recursive closures in JavaScript

No, at most two instances of function's local data will be held in memory at any given point in time. Here is the order of events:

animate(0) is called.
A closure with param == 0 is created, it now prevents this variable from being released.
Timeout fires, animate(1) is called.
New closure with param == 1 is created, it now prevent this variable from being released.
The first closure finishes executing, at this point it is no longer referenced and can be released. The local variables from the first animate() call can also be released now.
Repeat starting with step 3, now with animate(2).

Javascript closure returning a recursive function

Perhaps you're confused by the outermost function that is being invoked immediately. This serves only to protect current in a variable scope. If we eliminate that, it's probably clearer.

var current = -1;
var next = function() {// This is what would have been returned in the original
    current += 1;
    if (current < 10) {
        console.log(current);

        next();       // recursive call 
    } else {
        return;
    }
};

next();

Now you have the same as the original code, except that current isn't in its own scope. As you can see, the function is simply assigned to the next variable.

That's exactly what's happening in the original, except that in the original the outer function exists and is immediately invoked. That outer function is a one-time-shot function, and is not assigned to next, though its return value is.

JavaScript doesn't have block scope (yet), but if it did, think of it as being similar to this:

var next;

{ // Create a (fictional) variable scope that has `current` and the function

    var current = -1;

    next = function() {
        current += 1;
        if (current < 10) {
            console.log(current);

            next();       // recursive call 
        } else {
            return;
        }
    };

}

next();

But since JS doesn't have block scope, but only function scope, we need to emulate this with a function.

We can tweak the original just a little to make it look similar.

var next;

(function() { // Create a variable scope that has `current` and the function

    var current = -1;

    next = function() {
        current += 1;
        if (current < 10) {
            console.log(current);

            next();       // recursive call 
        } else {
            return;
        }
    };

}());

next();

Closures with recursion JavaScript

Yes, you're not using the functional paradigm.

In your case you're using the recursion just to loop and the processing is done using variables that are outside of the function. It's really not much different than using global variables (except that they're not global but locals of the outside function).

To reverse a string using the functional approach you should consider that the reverse of a string is composed by last_char + (reverse of middle part) + first_char.
This definition expands naturally into a recursive function... for example:

function rev(str) {
    if (str.length < 2) {
        // Empty string or a single char... reverse = input
        return str;
    } else {
        return str[str.length-1] + rev(str.slice(1, -1)) + str[0];
    }
}

this uses no explicit state (as you may notice there are no assignments at all).

If you're looking for a tail-call optimizable version instead consider:

function rev(todo, done) {
    if (todo === "") {
        return done;
    } else {
        return rev(todo.slice(1), todo[0] + (done||""));
    }
}

the idea in this case is that the processing case must be return <recursive-call> (in the previous example this is not happening because the result of recursion is added one char to each end before returning).

If your code ends up returning the unprocessed result of a recursive call then the function can be tail-call optimized as no stack space is needed. In other words the recursive call becomes a simple loop.

Finally this is another version, not purely functional but that seems similar to what you're attempting:

function rev(str) {
    function rev1(v, i, j) {
        if (i >= j) {
            return v.join("");
        } else {
            var t=v[i]; v[i]=v[j]; v[j]=t;
            return rev1(v, i+1, j-1);
        }
    }
    return rev1(str.split(""), 0, str.length-1);
}

This is not purely functional because the vector elements are swapped (and you can see there are assignments) but uses a tail-call optimizable recursion to do the loop. Note that rev1 is not a closure but a function (captures no state and you can also put it outside of rev).

Is it possible to make a recursive closure in Rust?

There are a few ways to do this.

You can put closures into a struct and pass this struct to the closure. You can even define structs inline in a function:

fn main() {
    struct Fact<'s> { f: &'s dyn Fn(&Fact, u32) -> u32 }
    let fact = Fact {
        f: &|fact, x| if x == 0 {1} else {x * (fact.f)(fact, x - 1)}
    };

    println!("{}", (fact.f)(&fact, 5));
}

This gets around the problem of having an infinite type (a function that takes itself as an argument) and the problem that fact isn't yet defined inside the closure itself when one writes let fact = |x| {...} and so one can't refer to it there.

Another option is to just write a recursive function as a fn item, which can also be defined inline in a function:

fn main() {
    fn fact(x: u32) -> u32 { if x == 0 {1} else {x * fact(x - 1)} }

    println!("{}", fact(5));
}

This works fine if you don't need to capture anything from the environment.

One more option is to use the fn item solution but explicitly pass the args/environment you want.

fn main() {
    struct FactEnv { base_case: u32 }
    fn fact(env: &FactEnv, x: u32) -> u32 {
        if x == 0 {env.base_case} else {x * fact(env, x - 1)}
    }

    let env =  FactEnv { base_case: 1 };
    println!("{}", fact(&env, 5));
}

All of these work with Rust 1.17 and have probably worked since version 0.6. The fn's defined inside fns are no different to those defined at the top level, except they are only accessible within the fn they are defined inside.

Calling completion handler within nested closure to stop recursive function

Regardless of whether you need recursion or not, for an async call you'd need a completion handler, so that the caller can know when the operation has completed.

If you want to use recursion, you can pass the completion handler down to the next recursive invocation, and call it when completed.

func getResults(onCompleted handler: @escaping () -> Void) {
   loadResults { pageReturned in
      let needToLoadMore = ... // determine if you need to load more pages
      // other side effects
      
      if needToLoadMore {
         getResults(onCompleted: handler)
      } else {
         handler()
      }
   }
}

Function signature for returning a recursive closure

Because Rust supports recursive types, you just need to encode the recursion in a separate structure:

enum Msg { 
    Inc,
    Dec,
}

// in this particular example Fn(Msg) -> F should work as well
struct F(Box<FnMut(Msg) -> F>);

fn counter(state: i32) -> F {
    F(Box::new(move |msg| match msg {
        Msg::Inc => {
            println!("{}", state);
            counter(state + 1)
        }
        Msg::Dec => {
            println!("{}", state);
            counter(state - 1)
        }
    }))
}

fn main() {
    let mut c = counter(1);
    for _ in 0..1000 {
        c = c.0(Msg::Inc);
    }
}

We cannot do away with boxing here, unfortunately - since unboxed closures have unnameable types, we need to box them into a trait object to be able to name them inside the structure declaration.

How do I create an _inline_ recursive closure in Swift?

There is a workaround:

func unimplemented<T>() -> T
{
    fatalError()
}

func recursive<T, U>(f: (@escaping (((T) -> U), T) -> U)) -> ((T) -> U)
{
    var g: ((T) -> U) = { _ in unimplemented() }

    g = { f(g, $0) }

    return g
}

recursive is a function that takes a closure (((T) -> U), T) -> U, where ((T) -> U) is a reference to a stripped version of the closure, and returns a usable function, g.

g is initially assigned a fake function (which crashes upon call). This is done to enable recursion for a new value of g, where g is passed to f along with an input value of T. It is important to note that g in g = { f(g, $0) } refers to itself, and not the fake function assigned to it earlier. So whenever the ((T) -> U) parameter is referenced in f, it is a reference to g, which in turn references itself.

This function allows for inline recursion such as in the following:

recursive { f, x in x != 10 ? f(x + 1) : "success" }(0)

This function recurs a total of 11 times, without the need to declare a single variable.

Update: This now works with Swift 3 preview 6!

Personally speaking for a moment here, I find this to be a rather elegant solution because I feel that it simplifies my code to the bare minimum. A Y combinator approach, such as the one below

func recursive<T, U>(_ f: (@escaping (@escaping (T) -> U) -> ((T) -> U))) -> ((T) -> U)
{
    return { x in return f(recursive(f))(x) }
}

would have me return a function, an escaping closure within an escaping closure at that!

recursive { f in { x in x != 10 ? f(x + 1) : "success" } }(0)

The code above would be invalid if not for the inner @escaping attribute. It also requires another set of braces, which makes it look more verbose than what I'm comfortable with when writing inline code.