1、 go语言函数返回过程
首先需要明白go语言函数的返回过程
借助defer关键字，我们了解到关键字return不是一个原子操作，实际上return只代表汇编指令ret，即跳转程序执行。比如语句 return i，实际上分两步执行，即首先将i值存入栈中作为返回值，然后执行跳转，而defer的执行时机正是在跳转前。
2、go函数调用规范
在Go汇编语言中CALL指令用于调用函数，RET指令用于从调用函数返回。但是CALL和RET指令并没有处理函数调用时输入参数和返回值的问题。CALL指令类似PUSH IP和JMP somefunc两个指令的组合，首先将当前的IP指令寄存器的值压入栈中，然后通过JMP指令将要调用函数的地址写入到IP寄存器实现跳转。而RET指令则是和CALL相反的操作，基本和POP IP指令等价，也就是将执行CALL指令时保存在SP中的返回地址重新载入到IP寄存器，实现函数的返回。
Go 通过栈传递函数的参数和返回值，在调用函数之前会在栈上为返回值分配合适的内存空间，随后将入参从右到左按顺序压栈并拷贝参数，返回值会被存储到调用方预留好的栈空间上，我们可以简单总结出以下几条规则：
1、通过堆栈传递参数，入栈的顺序是从右到左，而参数的计算是从左到右；
2、函数返回值通过堆栈传递并由调用者预先分配内存空间；
3、调用函数时都是传值，接收方会对入参进行复制再计算；
3、 递归函数的调用
有了以上两点的铺垫，从本质上讲递归函数与普通函数并无特殊之处，只是不断调用自身，栈不断增加而已。
写这篇博客的原因是因为刷在二叉树的层序遍历这道算法题时，使用了dfs算法，从根节点开始，在递归时需要分别访问左、右子树，因为代码是按照顺序执行的，什么时候返回？究竟是如何利用递归得到最终解的？于是便对go的递归函数调用有了兴趣，其实递归算法在你不知到函数是如何进行调用时，是比较难在脑海中构思的，最早的想法是队列，因为代码一般是按照顺序执行的，结合队列的先进先出，很合适，但仔细思考和验证时，发现并不是。
下面是我对该问题的简单验证
4、层序遍历的dfs算法
type tree struct {
val int
left, right *tree
}
func dfs(tr *tree, level int, res [][]int) [][]int {
//1、递归终止条件
if tr == nil {
return res
}
//2、处理当前层
if len(res) == level {
res = append(res, []int{tr.val})
} else {
res[level] = append(res[level], tr.val)
}
//3、下转
fmt.Println(level, tr.val, len(res), res)
res = dfs(tr.left, level+1, res)
res = dfs(tr.right, level+1, res)
return res
}
对于以下这颗满二叉树
使用dfs完成层序遍历后得到的输出结果如下：
level tr.val len(res) res
0 1 1 [[1]]
1 2 2 [[1] [2]]
2 4 3 [[1] [2] [4]]
2 5 3 [[1] [2] [4 5]]
1 3 3 [[1] [2 3] [4 5]]
2 6 3 [[1] [2 3] [4 5 6]]
2 7 3 [[1] [2 3] [4 5 6 7]]
res的值为：[[1] [2 3] [4 5 6 7]]
结合go函数调用规范，分析其实现原理，不过分纠结于实现细节，我猜测对于该递归算法应有如下流程：
每次函数调用时，Go 通过栈传递函数的参数和返回值，在调用函数之前会在栈上为返回值分配合适的内存空间，视为入栈操作，在处理完当前层的逻辑后，继续下转，当遇到空结点时，当前函数记录返回值，完成出栈操作。
