递归与递推

各种原因拖更了很久（确实不愧是叫dove），不多聊了，先写（氵）一期

还是多嘴几句吧，这一系列教程会参考很多视频和书籍，毕竟我就一个吊车尾），可以去B站看一下木子喵的视频，对于不少算法讲的很形象（而且声音很好听）。关于数据结构基础知识建议看看ghgg的博客（DS小入门），或者可以找一下《啊哈！算法》看一下（找不到可以来找我要），我主要来做一下算法方面，大概会基于紫书来写（别急我不是oier），顺便找点题（其实是预习应对蓝桥杯，毕竟去年捐款300历历在目）

先来讲递归

递归的定义：见“递归”

或许你没有理解，那我来解释一下

如果你还没有理解递归，请理解“递归”

好吧这是一个紫书的冷笑话，或许你现在还不明白，一会我来解释（当然一会你自己就看懂了

首先引入一个经典问题，汉诺塔问题

​给定三根柱子，记为A,B,C，其中A柱上有n个盘子，从上到下编号为1到n，且上面的盘子一定比下面的盘子小。问：将A柱上的盘子经由B柱移动到C柱最少需要多少次？

​ 移动时应注意：

① 一次只能移动一个盘子

​②大的盘子不能压在小盘子上

暴力枚举肯定极其浪费时间，那有没有别的方法呢？

我们不妨利用“子问题”的思路考虑，我们从结果可以知道，第n个盘子一定是C柱最下面的盘子，所以我们要首先把它移动到C柱，那我们应该怎么把它移过去呢？其实很简单，只需要两步：

  • 第一步，把上面的1到n-1个盘子都移动到B柱

  • 第二步，把第n个盘子移动到C柱

这不有手就行？你看，没骗你们，很简单吧（别揍我

其实这里就利用了“子问题”的思路，将把第n个盘子移动到C柱分解为两个子问题，第一个子问题就是把上面的1到n-1个盘子都移动到B柱，第二个子问题是把第n个盘子移动到C柱，于是你会发现汉诺塔问题很简单，只需要三步：

  • 第一步，把上面的1到n-1个盘子都移动到B柱

  • 第二步，把第n个盘子移动到C柱

  • 第三步，把B柱上面的1到n-1个盘子都移动到C柱

那我们发现，第一个子问题和第三个子问题实际上是一个问题，只是把A柱换成了B柱，把B柱换成了C柱，而第二个子问题属于是有手就行。那至于怎么解决第一个子问题，毕竟问题不解决它也不会跑，所以建议留给明天的自己（真诚脸）

如果你是一个听话的人，这时候你应该刚刚睡醒并且想起来似乎你有n-1个盘子要从A柱搬到B柱。但是刚刚睡醒的你觉得似乎有什么不对，好像你昨天已经把n个盘子搬走了，今天好像干的活一样，只不过是少搬了一个，以及柱子的编号换了一下。于是你选择继续睡觉，把活交给昨天的自己来干，毕竟昨天的你都可以搬n个盘子，搬n-1个肯定不在话下。如果你是这么想的，恭喜你，下课！

好吧我来解释一下，今天的你用了昨天的你做了一个相似的事，其实这就是“递归”，即问题A的子问题中有与问题A几乎一样的问题，此时就可以使用递归的思想。

递归思想的难点就在于理解如何分解出“子问题”，以及如何调用“自己”，毕竟我们是在给计算机下命令，所以不能按照人类的思考方式，而是应该去从计算机的处理方式思考。

木子喵视频里面总结的很精炼，引用一下：递归思想就是将未知的问题缩小，直到访问到已知问题，便开始返回值，最后解决我们的问题。

人类的本质是套娃，递归的本质也是

现在你应该理解了上面的冷笑话——递归的定义：见“递归”。因为递归不正是调用自己吗（

在编程中，函数可以调用另一个函数。而一个函数调用了自己，就是递归。

用阶乘举例说明一下吧，先给出阶乘的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f(int a)
{
    if(a > 0)
      return a*f(a-1);
    else
      return 1;  //注意f(0)是1
}


//翻书发现了一种更简单的写法，显得我很呆

int f(int a)
{
    return a == 0 ? 1 : a*f(a-1)
}

这里就在函数f(x)里面调用了f(x)

递归好用，但是一定要记得写终止条件，不然无限递归······TLE大家族欢迎你

对没错，TLE=Time Limit Enough=时间充裕

递归还有一个隐患，就是爆栈，即栈溢出。因为每次调用函数都是会在调用栈增加一个栈帧，而调用栈所在的堆栈段是有大小限制的，久而久之可能就会出现越界访问，出现段错误。当然，栈溢出不一定完全是因为递归调用次数太多，也有可能是局部变量过大（因为局部变量也是放在堆栈段）。所以可以使用全局变量解决一部分栈溢出问题。

我们回过头来解决汉诺塔问题，给出代码

1
2
3
4
5
6
7
8
9
10
11
12
int move(int n, char a, char b, char c)
{
    if (n == 0)
        return 0;//一定记得写终止条件
    else
    {
        move(n - 1, a, c, b);//将n-1个盘子移动到工具柱b
        printf("%c -> %c \n", a, c);//将第n个盘子移动到目标柱c
        move(n - 1, b, a, c);//将n-1个盘子移动到目标柱c
        return 0;
    }
}

现在是递推时间

递归，是由未知问题通过分解为“子问题”返回已知问题，最后求解；递推，则是由已知问题推出未知问题。

这里引入一个经典的问题，兔子繁殖问题（斐波那契数列）。

自己百度吧，懒得码字了（

还有我知道你生物好，近亲交配致死率高可能没几只兔子活着，但是这是数学问题（恼

请问第n个月有几只兔子？

  1. 可以用递推（代码大致如下
1
2
3
4
5
6
7
8
9
10
int tuzi[100];
tuzi[0] = 1;
tuzi[1] = 1;
int f(int n)
{
    for(int i = 2;i <= n;i++)
    {
        tuzi[i] = tuzi[i-1] + tuzi[i-2];
    }
}
  1. 递归（代码大致如下
1
2
3
4
5
6
7
8
9
int f(int n)
{
    if(n == 0||n == 1)
        return 1;
    else
    {
        return f(n-1) + f(n-2);
    }
}

这里给一下洛谷题单递推与递归

如果有啥要补充的我再单独氵一篇博客

下一期大概率是DP