如何处理闭包递归性

Question

这是一个非常简单的递归函数：

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

如果我想将它转换为闭包：

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

我遇到了编译错误：“变量在其自身的初始值中使用”

- Luc-Olivier

Answer 1

您可以通过两步赋值来解决这个问题。

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

或者你可以使用Y组合器，了解更多

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) }
}

---

这是一个解决@zneak发现的内存泄漏问题的方法（它没有内存泄漏，但捕获了错误的值）

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")
    }
}

- Bryan Chen

---

谢谢。我发布另一个解决方案。 - Luc-Olivier

请注意，您的第一个示例应为 var lap: ((Int) -> Int)!。它可以正常工作，但如果您将返回类型设置为 void，编译器将抱怨代码块实际上没有返回 void。 - Matej

Answer 2

编辑：使用嵌套函数，Swift 2 已解决此问题。苹果建议使用以下代码：

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) }

尽管从当前示例中不容易看出来，但所谓的局部函数捕获了封闭作用域中的局部变量。

使用局部函数不会泄漏，而闭包会。然而，在这种情况下，lap 无法被重新分配。

我收到了苹果公司的 Joe Groff 发来的电子邮件，说明他们仍计划在以后实现将闭包作为弱可变变量捕获的功能。然而，这确认了目前除了使用局部函数外没有其他方法可以实现。

---

您当前的解决方案存在内存泄漏问题： lap 的闭包对自身有一个强引用，意味着它永远不会被释放。您可以通过在附加了泄漏检查工具的情况下运行以下程序进行验证：

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)
}

不幸的是，由于显式捕获语法无法应用于闭包类型（您会收到一个错误，提示“'unowned' 无法应用于非类类型 '(Int) -> Int'”），因此似乎没有简单的方法可以在不泄漏的情况下实现这一点。我已经提交了错误报告。

- zneak

---

有趣的是，我从未考虑过它可能会导致内存泄漏。我想知道我的 Y-combinator 解决方案是否有同样的问题？ - Bryan Chen

我发现了一个解决我的回答中显式捕获语法问题的方法。 - Bryan Chen

这是一个优雅的解决方案，解决了一个小问题，非常感谢！有人知道弱闭包是否有更新吗？ - MandisaW

Answer 3

这是我对自己问题的回答：

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

- Luc-Olivier

---

实际上，{ $0 ) 是不必要的。由于某种原因，在编写实际闭包块单词之前声明类型。var lap: (Int) -> Int 应该可以正常工作。 - funct7

@BridgeTheGap 晚了两年的评论，但我觉得这个评论是错误的。实际上编译器抱怨 var lap 没有被初始化，只是被声明了。 - aneuryzm

Answer 4

这个怎么样？

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

这很简单，我只是在闭包内定义了一个递归本地函数，该函数返回该函数。

然而，我必须说，@Bryan Chen关于Y组合子的答案非常棒。

- FranMowinckel

Answer 5

我曾经遇到相同的问题，但对于那些已有的东西都不满意，所以我创建了一个库，并将其放在GitHub上。

使用这个库（用 Swift 3.0），你的代码会像这样：

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

- riisemichi