go语言的递归函数调用

Zppj · · 302 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

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函数调用规范，分析其实现原理，不过分纠结于实现细节，我猜测对于该递归算法应有如下流程：