Swift是否实现了尾调用优化？在相互递归的情况下呢？

Question

Swift是否实现了尾调用优化？在相互递归的情况下呢？

76

特别是如果我有以下代码：

func sum(n: Int, acc: Int) -> Int {
  if n == 0 { return acc }
  else { return sum(n - 1, acc + n) }
}

Swift编译器会将其优化为循环吗？在下面更有趣的情况下是否也是这样？

func isOdd(n: Int) -> Bool {
  if n == 0 { return false; }
  else { return isEven(n - 1) }
}

func isEven(n: Int) -> Bool {
  if n == 0 { return true }
  else { return isOdd(n - 1) }
}

- Alfa07

2

栈的大小是有限的。当您运行一个无限递归函数时会发生什么？它会崩溃吗？ - Veedrac

@Veedrac：这是苹果。它将被转换为一个循环，并返回一个确定性结果。 - Mare Infinitus

5

@Veedrac - 这是一种普遍情况。但一个进行无限递归的函数式程序员就像一个没有测试子句的命令式程序员做for循环，例如 for (int i = 0; ; i++) { println("%d", i); }。 - Yawar

@Yawar 我不明白你的观点是什么。 - Veedrac

6

我的观点是，一个函数式程序员不太可能出现无限递归的情况，就像一个命令式程序员不太可能出现无限循环的情况一样。 - Yawar

3

关于独立问题“Swift是否实现尾调用优化(TCO)？”的简短回答是：“Swift不保证对尾调用进行优化，因此不能依赖它。” 然而，如果你正在做递归，那么可以尝试使用TCO，因为编译器可能会提供帮助 ;) - arcseldon

2个回答

26

是的，在某些情况下，Swift编译器会执行尾递归优化：

func sum(n: Int, acc: Int) -> Int {
    if n == 0 { return acc }
    else { return sum(n - 1, acc: acc + 1) }
}

作为全局函数，该函数在“Fastest”优化级别 (-O) 下将使用恒定的堆栈空间。

如果它在结构体中，则仍将使用恒定的堆栈空间。然而，在类内部，编译器不执行尾递归优化，因为该方法可能会在运行时被覆盖。

Clang 也支持 Objective-C 的尾递归优化，但通常 ARC 在递归调用后调用 release，从而防止了这种优化，请参阅 Jonathan Mah 的这篇文章获取更多详细信息。

ARC 似乎也阻止了 Swift 中的 TCO：

func sum(n: Int, acc: Int, s: String?) -> Int {
    if n == 0 { return acc }
    else { return sum(n - 1, acc + 1, s) }
}

我的测试中没有进行TCO。

- Sebastian

你的意思是，Jonathon Mah 描述的 Obj-C 的相同 TCO 注意事项也适用于当前（1.0）版本的 Swift 编译器吗？ - Palimondo

@Palimondo 很遗憾，这就是我看到的。 - Sebastian

7

我不会说ARC防止尾递归优化，相反，由于ARC必须在函数返回之前添加释放调用，因此递归调用不再处于尾部位置。 - Ferruccio

@Sebastian，从我的理解来看，TCO适用于不涉及引用的情况，即在结构体上调用函数和方法是可以的，但是在类的方法上调用会被释放，因此无法优化？或者说函数是通过引用复制的，因此受到ARC的影响？ - Gerome Bochmann

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ferruccio · Accepted Answer

最好的方法是检查编译器生成的汇编代码。我使用以下代码进行编译：

swift -O3 -S tco.swift >tco.asm

输出结果的相关部分

.globl    __TF3tco3sumFTSiSi_Si
    .align    4, 0x90
__TF3tco3sumFTSiSi_Si:
    pushq    %rbp
    movq    %rsp, %rbp
    testq    %rdi, %rdi
    je    LBB0_4
    .align    4, 0x90
LBB0_1:
    movq    %rdi, %rax
    decq    %rax
    jo    LBB0_5
    addq    %rdi, %rsi
    jo    LBB0_5
    testq    %rax, %rax
    movq    %rax, %rdi
    jne    LBB0_1
LBB0_4:
    movq    %rsi, %rax
    popq    %rbp
    retq
LBB0_5:
    ud2

    .globl    __TF3tco5isOddFSiSb
    .align    4, 0x90
__TF3tco5isOddFSiSb:
    pushq    %rbp
    movq    %rsp, %rbp
    testq    %rdi, %rdi
    je    LBB1_1
    decq    %rdi
    jo    LBB1_9
    movb    $1, %al
LBB1_5:
    testq    %rdi, %rdi
    je    LBB1_2
    decq    %rdi
    jo    LBB1_9
    testq    %rdi, %rdi
    je    LBB1_1
    decq    %rdi
    jno    LBB1_5
LBB1_9:
    ud2
LBB1_1:
    xorl    %eax, %eax
LBB1_2:
    popq    %rbp
    retq

    .globl    __TF3tco6isEvenFSiSb
    .align    4, 0x90
__TF3tco6isEvenFSiSb:
    pushq    %rbp
    movq    %rsp, %rbp
    movb    $1, %al
LBB2_1:
    testq    %rdi, %rdi
    je    LBB2_5
    decq    %rdi
    jo    LBB2_7
    testq    %rdi, %rdi
    je    LBB2_4
    decq    %rdi
    jno    LBB2_1
LBB2_7:
    ud2
LBB2_4:
    xorl    %eax, %eax
LBB2_5:
    popq    %rbp
    retq

在生成的代码中没有调用指令，只有条件跳转(je/jne/jo/jno)。这明显表明Swift在两种情况下都会进行尾调用优化(TCO)。

此外，isOdd/isEven函数很有趣，因为编译器不仅似乎执行TCO，而且在每种情况下也内联其他函数。