讲讲递归和尾递归

递归

理解递归，就是要先理解递归，递归的特性有两个。

• 调用自身
• 有明确的函数出口

比如求一个n！的阶乘是很容易写成递归的。

func fact(x int) int {
    if x == 1 {
        return 1 // 函数出口
    } else {
        return x * fact(x-1) // 递归本身
    }
}

假设我们求fact(3)的值，我可以如下图一般展开，显而易见的是函数会在x==1处返回，然后从调用栈的最深处返回开始的调用位置，并且返回阶乘的结果。

尾递归

尾递归函数的返回值返回的是函数本身， 尾递归的性质

• 不产生函数调用栈，不会出现stackoverflow
• 调用自身在函数的尾部

下面是一段二分search的尾递归形式

var i int = 1
// 使用递归去实现这个过程
// 确切的说这是一个尾递归（不保存调用者的状态，直接丢弃）
func binarySearchRecursive(start, end int, in []int, target int) int {
    fmt.Println("------------------------------------------------------------------------")
    fmt.Printf("if start %d == end %d\n", start, end)
    fmt.Printf("frame %v: start: %d, end: %d, in: %v, target: %d\n", i, start, end, in, target)
    fmt.Println("call binarySearchRecursive")
    fmt.Println("------------------------------------------------------------------------")
    i++
    if start == end {
        return start
    }
    if start != end {
        mid := (start + end) / 2
        if target > in[mid] {
            start = mid + 1
        } else {
            end = mid
        }
    }
    return binarySearchRecursive(start, end, in, target)
}

红色方向表示函数栈的方向，可以把他理解成串行之行，上一次执行的输出是一个执行的输入，所以很显然这种写法是不存在调用栈。