学习递归的一些总结

柔光的暖阳◎ 2022-12-17 14:51 158阅读 0赞

# 学习递归的一些总结 #

## 1 什么是递归 ##

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

## 2 递归的基本原理 ##

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

## 3 递归的优缺点 ##

### 3.1 优点 ###

*  实现简单
 *  可读性好

### 3.2 缺点 ###

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

## 4 递归的三大要素 ##

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

> 先不管函数里面的代码什么，而是要先明白，你这个函数的功能是什么，要完成什么样的一件事。 例如，我定义了一个函数，代码如下
> 
>     func jieshen(n int) int{ 
>         //计算阶乘的具体方法
>     }

### 4.2 寻找递归结束条件 ###

> 所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出**递归的结束条件**，不然的话，会一直调用自己，进入无底洞。 我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。
> 
>     func jieshen(n int) int { 
>     	if n<=2 { 
>     		return n
>     	}
>         //f(n)的通用方法
>     }

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

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

![递归调用的过程][4d157c717a36517f6ea599eb0b13236c.png]

## 5 常见递归练习 ##

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

### 5.1 第一递归函数功能 ###

func f(n int) int { 
       
    }

### 5.2 找出递归结束条件 ###

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

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

### 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)
    }

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

答是不大对，当 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)
    }

### 5.4 思考 ###

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

[4d157c717a36517f6ea599eb0b13236c.png]: /images/20221122/624c6a3d1d764e9ea70005ff6d43cc2c.png