How to handle closure recursivity

Question

Here's a very simple recursive function:

func lap (n: Int) -> Int {
    if n == 0 { return 0 }
   return lap (n - 1)
}

If I want to convert it as closure:

let lap = {
    (n: Int) -> Int in
    if n == 0 { return 0 }
    return lap (n - 1)
}

I got a compiler error: "Variable used within its own initial value"

score 14 · Answer 1 · edited May 23 '17 at 11:47

you can workaround it with two step assignment

var lap : (Int) -> Int!
lap = {
    (n: Int) -> Int in
    if n == 0 { return 0 }
    return lap(n - 1)
}

or you can use Y combinator

func Y<T, R>( f: (T -> R) -> (T -> R) ) -> (T -> R) {
    return { t in f(Y(f))(t) }
}

let lap = Y {
    (f : Int -> Int) -> (Int -> Int) in
    return { (n : Int) -> Int in return n == 0 ? 0 : f(n - 1) }
}

// with type inference 
let lap2 = Y {
    f in { n in n == 0 ? 0 : f(n - 1) }
}

~~This is a workaround of the memory leak problem that @zneak found~~ (It doesn't have memory leak but captured the wrong value)

func f(n: Int) {
    var f = Foo()
    var lap: @objc_block (Int)->Int = { $0 }
    var obj: NSObject = reinterpretCast(lap)
    lap = {
        [weak obj] (n: Int) -> Int in // unowned will cause crush
        if n == 0 { return 0 }
        println(f)
        var lap2 : @objc_block (Int)->Int = reinterpretCast(obj)
        return lap2 (n - 1)
    }
    lap(n)
}

for i in 0..<5 {
    f(i)
}

class Foo {
    init() {
        println("init");
    }

    deinit {
        println("deinit")
    }
}

note that your first example should be `var lap: ((Int) -> Int)!`. It works as is but if you have `void` as return, the compiler will complain about not actually returning `void` in your code block. — Matej, May 05 '15 at 18:03

zneak · Answer 2 · 2018-05-01T22:31:09.227

EDIT This has been resolved with Swift 2 using nested functions. Apple suggests this code:

func f(n: Int) {
    func lap(n: Int) -> Int {
        if n == 0 { return 0 }
        print(n)
        return lap(n - 1)
    }
    lap(n)
}

for i in 0..<1000000 { f(i) }

Although this is not obvious from the current example, so-called local functions capture the locals of the enclosing scope.

Using a location function does not leak, whereas a closure would. However, clearly, lap can't be reassigned in this case.

I received an email from Apple's Joe Groff stating that they still plan on making it possible to capture closures as weak and mutable variables at a later point. This does confirm, however, that there's no way to do it right now except with a local function.

Your current solution has a memory leak in it: lap's closure has a strong reference to itself, meaning that it cannot ever be released. This can easily be verified by launching the following program with the Leaks instrument attached:

import Foundation

func f(n: Int) {
    var lap: (Int)->Int = { $0 }
    lap = {
        (n: Int) -> Int in
        if n == 0 { return 0 }
        println(n)
        return lap (n - 1)
    }
    lap(n)
}

for i in 0..<1000000 {
    f(i)
}

Unfortunately, as the explicit capture syntax cannot be applied to closure types (you get an error that says "'unowned' cannot be applied to non-class type '(Int) -> Int'"), there appears to be no easy way to achieve this without leaking. I filed a bug report about it.

Interesting, I never consider it may cause memory leak. I wonder does my Y-combinator solution have same problem? — Bryan Chen, Aug 03 '14 at 10:39
I found a hack to workaround the explicit capture syntax problem in [my answer](http://stackoverflow.com/a/25103566/642626). — Bryan Chen, Aug 03 '14 at 10:57
Such an elegant solution to an odd little problem, thanks! Does anyone know if there has been an update on weak closures? — MandisaW, May 01 '18 at 22:09

score 4 · Answer 3 · answered Aug 03 '14 at 10:13

4

Here's a response to my own question:

var lap: (Int)->Int = { $0 }
lap = {
    (n: Int) -> Int in
    if n == 0 { return 0 }
    println(n)
    return lap (n - 1)
}

answered Aug 03 '14 at 10:13

Luc-Olivier

3,715
2
29
29

Actually, `{ $0 )` is unnecessary. For some reason, declaring the type before writing the actual closure block words. `var lap: (Int) -> Int ` should work fine – funct7 Dec 28 '15 at 07:21
@BridgeTheGap Late comment 2 years after, but this comment seems wrong to me. Indeed compiler is complaining that var lap is not initialized, but just declared. – aneuryzm Mar 16 '17 at 10:18

score 0 · Answer 4 · answered Jul 10 '16 at 14:43

What about this:

let lap = {(Void) -> ((Int) -> Int) in
   func f(n: Int) -> Int {
      print(n)
      return n == 0 ? 0 : f(n - 1)
   }
   return f
}()

It's quite simple, I've just defined a recursive local function inside a closure which returns the function.

However, I have to say that the answer from @Bryan Chen about the Y combinator is awesome.

score 0 · Answer 5 · answered Nov 26 '16 at 01:10

I had the same problem and was not statisfied with anything that was out there, so I created a library and made it available on GitHub.

Using this library (with Swift 3.0) your code would look like this:

let lap = Recursion<Int, Int> { (n, f) in
    n == 0 ? 0 : f(n-1)
}.closure

How to handle closure recursivity

5 Answers5

Linked

Related