前两题看到面试题中出现了递归回溯，当时心里没想出来，也是一阵苦逼，直接GG。今天回过头来重新复习复习，一下包含两道递归简单和一个回溯中等。时间上同样是对自己做了要求。来，下面开始上题：
斐波那契数列
虽然简单，但是经典啊！现在让大家手写，能手写出来吗？这其中包含的是递归的魅力，题目我就不再赘述了，下面我就直接上码了：
func fib(N int) int {
if N == 0 {
return 0
}
if N == 1 {
return 1
}
return fib(N-1) + fib(N-2)
}
方法和思想都能简单，注意体会，每个数都是前两个数之和。
爬楼梯
这也是到简单的题目，使用的方法也和上面的题目一样，但是还是不能轻敌哈，题目的意思是，输出N，标识有N级台阶，限制是每次能爬一阶或者两阶，输出爬完N阶能够使用的方法次数。
是不是和斐波那锲很想呢？是的。当时有个思想误区：爬完楼梯的方法，每次爬方法加上下次能爬的方法，例如：爬3阶=先爬2阶+再爬1阶。这是个思想误区，当时从斐波那契回来，就惯性思维了这么想象。正确的是：爬3阶= 第一次爬2阶的方法+第一次还可以只爬一阶的方法。每次有两个选择，使用每次的两个选择递归。下面上码：
func climbStairs(n int) int {
if n == 0 {
return 1
}
if n < 0 {
return 0
}
var mem = make(map[int]int)
return climb(n-1, mem) + climb(n-2, mem)
}
func climb(n int, mem map[int]int) int {
if n == 0 {
return 1
}
if n < 0 {
return 0
}
if r, ok := mem[n]; ok {
return r
}
r := climb(n-1, mem) + climb(n-2, mem)
mem[n] = r
return r
}
上面的代码是在做了一次优化之后输出的，因为题目对时间有限制，无脑的递归固然是可以解决问题，但是时间限制过不去，这里使用map记录了每次对应的楼梯的使用方法，避免了重复的递归。主要还是了解其中的递归的作用，认真体会。
全排列
然后这这道中等的全排列题目，题目的意思也很简单，就是输入数组，输出全排列后的二维数组。不错，也是用到的递归，有个小点是去重，这样就OK了。下面上码：
package main
func permute(nums []int) [][]int {
if len(nums) == 0 {
return nil
}
var r [][]int
var info = make([]int, 0, len(nums))
mem := make(map[int]struct{})
_permute(nums, mem, &r, info)
return r
}
func _permute(num []int, mem map[int]struct{}, rInfos *[][]int, rInfo []int) {
if len(rInfo) == len(num) {
*rInfos = append(*rInfos, append([]int{}, rInfo...))
return
}
for _, v := range num {
if _, ok := mem[v]; ok {
continue
}
rInfo = append(rInfo, v)
mem[v] = struct{}{}
_permute(num, mem, rInfos, rInfo)
delete(mem, v)
rInfo = rInfo[:len(rInfo)-1]
}
}
大致思路就是每次递归都遍历数组，为了避免重复，使用map记录下了每次记录的数子，知道数组长度和输入数组长度一致是给二维数组添加，添加的时候有个小点，append的时候不能直接append当前的以为数组rInfo，应为切片的底层时间还是数组，这样append造成的结果就是二维数组里的结果是都是一个，所以这里重新创建了新切片。然后需要注意的就是每次遍历的时候对map的删除和当前以为数组的弹出。最后就是时间上的问题，做这道题总共花了16分钟，感觉要是面试，有点悬了！
下课！
