How do I create an _inline_ recursive closure in Swift? [duplicate]

Question

Recursion is trivial with global functions in Swift. For example:

func f()
{
    f()
}

However, a closure cannot refer to itself. For example:

var f: (Void -> Void) =
{
    f()
}

yields the following error:

Variable used within its own initial value

Is there a workaround to this? How can I create a recursive closure inline?

Answer 1

Restriction is that two objects cannot be instantiated at the same time and refer to each other. One has to be created before the other. You can mark the function implicitly unwrapped optional. This way you initialize the function with nil, but "promise" that it will have a value later.

var f: (Void -> Void)!

f = {
    f()
}

Update: Another approach without implicitly unwrapped optionals:

var f: (Void -> Void)

var placeholder: (Void -> Void) = {
    f()
}

f = placeholder

Answer 2

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.