关于 Swift 中尾递归的思考-一一网

内容启发：关于 Swift 中尾递归的思考^[4]——Thuyen’s corner。

点赞评论，希望能在你的帮助下越来越好

作者：@iOS成长指北，本文首发于公众号 iOS成长指北，欢迎各位前往指正

如有转载需求请联系我，记住一定要联系哦！！！

这是我参与更文挑战的第6天，活动详情查看：更文挑战

什么是递归以及什么是尾递归\调用

递归调用在开发过程中是一种常见的技术手段，用于实现对函数自身的调用。

人们常基于以下两种原因而使用递归：

使代码更短、更简洁
对高级结构体（树，图）进行结点遍历

当我们在一个函数的尾部调用函数自身的话，称为尾递归，调用其他函数则称为尾调用^[1]。

我们函数调用会在内存形成一个调用记录，又称为调用帧（call frame）^[2]，保存调用位置和内部变量等信息。这些调用帧在嵌套调用过程中会形成了调用栈（call stack）

大部分变成语言都会进行尾调用优化 ——Tail call optimization (TCO) 即只保留内层函数的调用记录，如果所有函数都是尾调用，那么完全可以做到每次执行时，调用记录只有一项，这将大大节省内存，这就是尾调用优化的意义^[3]。

递归非常耗费内存，因为需要同时保存成千上百个调用记录，很容易发生栈溢出错误。但对于尾递归来说，由于只存在一个调用记录，所以永远不会发生栈溢出错误。

一些函数式编程语言将其写入了语言规格，那么在 iOS 中存在这种优化吗？这种优化做了什么？

我们将研究的方向锁定为 Swift？请相信我，在 Objective-C 中这个问题的表现形式是类似的。

在 Debug 模式下的尾递归崩溃

思考以下代码，在默认的 Debug 模式下回发生什么？

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

_ = sumPrefix(1000000, 0)
复制代码

一个常规的操作，计算从 0 到 1000000 之和。

当我们运行当前项目，额？崩溃了

出现了EXC_BAD_ACCESS 错误，这个错误常见于向已释放内存发送消息或者试图访问一个已经被释放的内存段——segmentation fault。

请注意这里我们说的是默认的 Debug 模式下即不开启相关编译优化

但是当我们添加与 Release 模式相同的编译优化时，代码可以正常运行！

Swift 尾调用优化

我们来比较一下，未开启优化与开启优化的相同代码，其表现究竟有什么不同？

将代码转成汇编，当配置项为 -Onone 时，当前函数调用的现象是什么（为了行文做了一些删减）

_main:
	.cfi_startproc
	...
	callq	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	...
	.cfi_endproc

	.private_extern	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.globl	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.p2align	4, 0x90
main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register %rbp
	subq	$80, %rsp
	xorl	%eax, %eax
	leaq	-8(%rbp), %rcx
	...
	callq	_memset
	...
	callq	_memset
	...
	cmpq	$0, %rcx
	jne	LBB1_2
	...
	jmp	LBB1_5
LBB1_2:
	...
	callq	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	movq	%rax, -56(%rbp)
LBB1_5:
	movq	-56(%rbp), %rax
	addq	$80, %rsp
	popq	%rbp
	retq
LBB1_6:
	ud2
LBB1_7:
	ud2
	.cfi_endproc
复制代码

这里多个 _memset 函数的调用，在运行过程中明进行了内存的初始化操作。并且当n != 0 时调用 jne LBB1_2，执行 LBB1_2 中的方法，执行 callq main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int。

当我们运行函数时，会一直开辟新的栈空间，这样子最终会栈溢出，导致崩溃。

而当我们使用 Release 环境所启用的 -O 即 Optimize for Speed[O] 进行分析时：（并未删减）

_main:
	movl	$1000000, %eax
	xorl	%ecx, %ecx
	.p2align	4, 0x90
	
	.private_extern	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.globl	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.p2align	4, 0x90
main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int:
	pushq	%rbp
	movq	%rsp, %rbp
	movq	%rsi, %rax
	testq	%rdi, %rdi
	je	LBB1_5
	movq	%rdi, %rcx
	.p2align	4, 0x90
LBB1_2:
	decq	%rcx
	jo	LBB1_6
	addq	%rdi, %rax
	jo	LBB1_7
	movq	%rcx, %rdi
	testq	%rcx, %rcx
	jne	LBB1_2
LBB1_5:
	popq	%rbp
	retq
LBB1_6:
	## InlineAsm Start
	## InlineAsm End
	ud2
LBB1_7:
	## InlineAsm Start
	## InlineAsm End
	ud2
复制代码

对比发现：

开始优化后，没有 callq _memset
开启优化后，没有发现执行函数 sumPrefix 的指令 callq main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int

尾递归/调用优化可以重复利用栈空间，重用栈帧，不申请栈空间，增加效率的同时也保证了安全性。

一个值得注意的点是，当我们开启优化以后，我们没有在 main 函数中找到 sumPrefix 函数的调用，这是因为启用的 -O 即 Optimize for Speed[O] 的另一个优化点是编译器会进行内联优化。

内联优化

什么内联优化，即有些方法直接将其展开成函数体代码从而减少函数栈帧的申请，以其达到更快的性能。

MJ 在其 Swift 课中说递归调用并不会进行内联优化，从目前得到的汇编代码看来，尾递归/调用优化时，进行了内联优化。

我们关掉当前函数的内联优化，使用 @inline(never) 标记函数为永不进行内联。

@inline(never)
func sumPrefix(_ n: Int, _ acc: Int) -> Int {
  if n == 0 { return acc }
  return sumPrefix(n - 1, acc + n)
}
复制代码

然后我们 -O 导出汇编进行分析：（未删减）

_main:
	pushq	%rbp
	movq	%rsp, %rbp
	movl	$1000000, %edi
	xorl	%esi, %esi
	callq	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	xorl	%eax, %eax
	popq	%rbp
	retq

	.private_extern	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.globl	main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int
	.p2align	4, 0x90
main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int:
	pushq	%rbp
	movq	%rsp, %rbp
	movq	%rsi, %rax
	testq	%rdi, %rdi
	je	LBB1_5
	movq	%rdi, %rcx
	.p2align	4, 0x90
LBB1_2:
	decq	%rcx
	jo	LBB1_6
	addq	%rdi, %rax
	jo	LBB1_7
	movq	%rcx, %rdi
	testq	%rcx, %rcx
	jne	LBB1_2
LBB1_5:
	popq	%rbp
	retq
LBB1_6:
	## InlineAsm Start
	## InlineAsm End
	ud2
LBB1_7:
	## InlineAsm Start
	## InlineAsm End
	ud2

	.section	__TEXT,__swift5_entry,regular,no_dead_strip
	.p2align	2
l_entry_point:
复制代码

恩，出现了 callq main.sumPrefix(Swift.Int, Swift.Int) -> Swift.Int ，方法调用主体与关闭内联之前没有变化。

尾递归/调用优化实现原理：当函数 A 的最后一步是调用自身函数A时（或者调用其他函数B），此时，当前函数 A 的位置信息和内部变量已经不会再用到了，直接把函数 A 的栈帧交给函数 A（B）使用。

总结

在 Debug 模式中利用递归/嵌套调用时，一旦调用过深，就有可能出现栈溢出，导致崩溃。因为无法保证最大深度，所以在某些情况下可能会导致你的构建/调试发生崩溃。

这里我们的例子指的尾递归/调用，可能更符合常见的调用逻辑，你需要慎重考虑你的代码是否会引起过深的调用以及使用递归是否是最优选择。

Xcode 对于 Swift 的编译优化除了实现了尾递归/调用优化，而且递归函数来说，编译优化会执行内联优化。

对于 Objective-C 来说，同样会发崩溃：

- (NSInteger)sumPrefix:(NSInteger)n acc:(NSInteger)acc {
    if (n == 0) {
        return acc;
    }
    return [self sumPrefix:n - 1 acc: acc + n];
}
复制代码

你可以试试类似的方法探究一下。