Vatsal Manot Vatsal Manot - 3 months ago 47
Swift Question

How do I create a recursive closure in Swift?

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

func f()

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

var f: (Void -> Void) =

yields the following error:

Variable used within its own initial value

Is there a workaround to this?


There is a workaround:

func unimplemented<T>() -> T

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.