How do I create an _inline_ recursive closure in Swift?

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?

score 18 · Answer 1 · edited Apr 25 '19 at 10:47

18

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

edited Apr 25 '19 at 10:47

dbart

5,468
2
23
19

answered May 29 '15 at 07:27

Kirsteins

27,065
8
76
78

While this works, it is ugly and requires me to use optionals, which I would rather not do. – Vatsal Manot May 29 '15 at 07:30
1

There is no other choice I believe. The same approach is used for `@IBOutlet`. I believe this is the main reason implicitly unwrapped optionals are in the language. – Kirsteins May 29 '15 at 07:31
Take a look at my own answer. – Vatsal Manot May 29 '15 at 07:32
They promised there won't be header files in Swift, but how is that different from .h headers in C? – Tytus Suski Jun 19 '15 at 11:36
1

The update method gives the following error: `variable 'f' captured by a closure before being initialized – Guy Daher Sep 18 '17 at 10:00

Vatsal Manot · Accepted Answer · 2016-08-27T17:53:52.717

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.

How is this any better than Kirsteins' answer above? You've just added more boilerplate, and you're assuming that your recursive function is in the form of `(T -> U)` (so you have to do aerobatics with the type system if that's not the case). Though not an ideal solution, implicitly unwrapped optionals were introduced to the language for this specific reason. — Sasha Chedygov, Sep 08 '15 at 17:16
@SashaChedygov: If you take a look at the timestamps, you can see that this was the first answer to the question. My intent was to share my knowledge in a Q/A format. — Vatsal Manot, Sep 08 '15 at 17:43
@SashaChedygov: As for my solution, I was aiming for a strict inline recursion. — Vatsal Manot, Sep 08 '15 at 17:45

How do I create an _inline_ recursive closure in Swift?

2 Answers2

Linked