12

递归

什么是递归？

递归可以简单的理解是：自己调用自己，

我们也可以看成是 入栈和出栈 也就是FILO 最先进去的哪一层，却在最后才出来。这大概就是递归的一些思想。

举个简单的例子

package example

func example(x int)int{
	if x == 1 {
		return 1
	}
	t := example(x-1) // 入栈的过程
	t++ //出栈后的操作
	return t //返回值
}

// 当然我们可以简写为

func exampleM(x int)int{
	if x == 1 {
		return 1
	}
	return exampleM(x -1) + 1 // 这一步 就是 将 入栈 和出栈 以及 返回 以及 计算 （也就是 每个栈单位都进行+1的计算）合为一体
}

其中 F（n） = F（n-1） +1 就叫做 递推公式 x==1 就是出栈规则。

递归的条件

• 拥有递归公式

这一点是 说 每一层都和上一层是一样的动作，比如都+1 都 *1 等 并且 上下层 存在关系 这也是 递归公式的意义

fn = f（n-1）+1 （举例子）

• 拥有出栈条件

if xxx return 也就是不能无限循环，不然就爆内存了。

递归的时间复杂度

如果就是一条线的话 那么 时间复杂度 就是 n 如果是 两条线或者是 n条线的话 那么它的时间复杂度 就是 n^n 比如 如果是2叉 那么 就是2^n 时间复杂度。

注意事项

• 爆栈

• 重复运算 例如 整个计算中 f(4) 有很多次，我们只需要 记录每个值，看看在这个map中有没有有的话就直接使用这个值的值即可。

函数{
    t := T(x-1) + T(x-2)
	e[x] = t // 我们只需要 记录下 所有值的具体值 (这里 切记 不能 e[x] = 函数（x） 就直接 stack overflow了 因为就出不去了。)
	//所以 我们只需要指向 具体的数值即可。这样我们就获得了一套 所有的数值的map值，接下来对比只有有一样的套用即可。这样 可以省下 非常大的时间。
	return t
	}