# 递归总结

# 1 什么是递归

递归的含义

递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

# 2 递归的基本原理

每一级的函数调用都有自己的变量。
每一次函数调用都会有一次返回。
递归函数中，位于递归调用前的语句和各级被调用函数具有相同的执行顺序。
递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。
虽然每一级递归都有自己的变量，但是函数代码并不会得到复制。

# 3 递归的优缺点

# 3.1 优点

实现简单
可读性好

# 3.2 缺点

递归调用，占用空间大
递归太深，易发生栈溢出
可能存在重复计算

# 4 递归的三大要素

# 4.1 明确你这个函数想要干什么

明确函数作用

先不管函数里面的代码什么，而是要先明白，你这个函数的功能是什么，要完成什么样的一件事。例如，我定义了一个函数，代码如下

func jieshen(n int) int{
    //计算阶乘的具体方法
}

1
2
3

# 4.2 寻找递归结束条件

递归结束条件

所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞。我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。

func jieshen(n int) int {
	if n<=2 {
		return n
	}
    //f(n)的通用方法
}

1
2
3
4
5
6

# 4.3 找出函数的等价关系式

等价关系式

我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。这个等价关系式的寻找，可以说是最难的一步了，如果你不大懂也没关系，因为你不是天才，你还需要多接触几道题。上面阶乘的最终结果代码如下

 func jieshen(n int) int {
 	if n <= 2 {
 		return n
 	}
 	return n * jieshen(n-1)
 }

1
2
3
4
5
6

# 5 常见递归练习

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。根据三大要素进行一步步分析如下

# 5.1 第一递归函数功能

func f(n int) int {
   
}

1
2
3

# 5.2 找出递归结束条件

求递归结束的条件，你直接把 n 压缩到很小很小就行了，因为 n 越小，我们就越容易直观着算出 f(n) 的多少，所以当 n = 1时，你知道 f(1) 为多少吧？够直观吧？即 f(1) = 1。代码如下：

func f(n int) int {
    if n==1 {
        return 1
    }
}

1
2
3
4
5

# 5.3 找出函数的等价关系式

每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。

第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。

第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。

所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。至此，等价关系式就求出来了。于是写出代码：

func f(n int) int {
    if n==1 {
        return 1
    }
    return f(n-1)+f(n-2)
}

1
2
3
4
5
6

# 大家觉得上面的代码对不对？

答是不大对，当 n = 2 时，显然会有 f(2) = f(1) + f(0)。我们知道，f(0) = 0，按道理是递归结束，不用继续往下调用的，但我们上面的代码逻辑中，会继续调用 f(0) = f(-1) + f(-2)。这会导致无限调用，进入死循环。

这也是我要和你们说的，关于递归结束条件是否够严谨问题，有很多人在使用递归的时候，由于结束条件不够严谨，导致出现死循环。也就是说，当我们在第二步找出了一个递归结束条件的时候，可以把结束条件写进代码，然后进行第三步，但是请注意，当我们第三步找出等价函数之后，还得再返回去第二步，根据第三步函数的调用关系，会不会出现一些漏掉的结束条件。就像上面，f(n-2)这个函数的调用，有可能出现 f(0) 的情况，导致死循环，所以我们把它补上。代码如下：

func f(n int) int {
    //f(0) = 0,f(1) = 1，等价于 n<=2时，f(n) = n。
    if n<=2 {
        return n
    }
    return f(n-1)+f(n-2)
}

1
2
3
4
5
6
7

# 5.4 思考

有人可能会说，我不知道我的结束条件有没有漏掉怎么办？别怕，多练几道就知道怎么办了。

← docker文件操作 go语言面试题总结 →