敲黑板！递归设计算法设计的知识要点

      童鞋们好，昨天的直播课你学会了吗？今天，我们一起来复习一下昨天的知识点吧，敲黑板了！做好笔记哦，记得回答课后作业！

1、什么是递归？

      递归，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。也就是说，递归算法是一种直接或者间接调用自身函数或者方法的算法。

      通俗来说，递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

2、递归三大要素

      第一要素：明确你这个函数想要干什么。先不管函数里面的代码什么，而是要先明白，你这个函数的功能是什么，要完成什么样的一件事。

      第二要素：寻找递归结束条件。我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。

      第三要素：找出函数的等价关系式。我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。

3、递归的使用

      下面我们还看几个案例：

      案例一：计算1+2+。。。+100

      案例二：实现字符串逆序

      案例三：实现斐波那契数列

4、递归的优化方法

      1）避免重复计算

      在这个案例中，很多数据会被重复计算，影响效率。比如f(3) 被重复计算两次。

f(5) = f(4) + f(3)

f(4) = f(3) + f(2)

      如果使用递归时不优化，会有非常多的子问题被重复计算。因此，使用递归时，必须要考虑有没有重复计算，如果有，一定要把计算过的状态保存起来。

      记录在数组之前：程序耗时375毫秒

      记录在数组之后：程序耗时0-1毫秒

      2） 使用尾递归

      递归，一般是从上往下，直到到最底，再一层层把值返回。

      不过，当n比较大时，如当n=10000 时，那么必须要往下递归10000层直到n<=1 才将结果慢慢返回，如果n太大，可能栈空间会不够用。这时就可以用尾递归优化解决。

      以第一个案例为例，普通递归的计算次序：

      尾递归的计算次序：

      改成尾递归后：

      在传统递归中，典型的模型是首先执行递归调用，然后获取递归调用的返回值并计算结果。以这种方式，在每次递归调用返回之前，您不会得到计算结果。

      在尾递归中，首先执行计算，然后执行递归调用，将当前步骤的结果传递给下一个递归步骤。

      特别说明：这要求编译器能对尾递归进行优化，每次重用或说覆盖原来递归方法的栈，而不是新建栈。遗憾的是JAVA不支持尾递归的优化，JAVA的尾递归代码与普通递归无异。所以，JAVA中一般能用迭代就不用递归。

      案例四： 斐波那契数列的应用1- 爬楼梯

      该题在Leetcode上： https://leetcode-cn.com/problems/climbing-stairs/

课后作业

      题目：有一对兔子，从出生第3个月起，每个月都生一对兔子，出生的当月算第1个月，小兔子长到第3个月后，每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

      分析思路：

      兔子的规律为数列：1, 1, 2, 3, 5, 8, 13, 21 ….

      童鞋们请将答案写到 微信公众号【东软睿道】 留言区哦！