递归与递推 —— 跟WilliamYan一起学算法

『WilliamYanと一緒にプログラミングを学びました』へようこそ!今天我们来学习递归和递推。这两种算法常用来实现搜索和动态规划。话不多说,我们开始吧!

递推可以理解为动态规划的一种
动态规划本质上和记忆化搜索没有区别

递归

递归的核心就是在一个函数中调用本身;

递归的主要问题是判断边界(即递归出口)

系统栈

递归时会调用系统栈。

每递归一层,该函数会被压入系统栈并执行下一层递归;下一层递归返回后,该层从系统栈中弹出,继续执行。

因此,递归时需要注意深度和每一层所需空间

关于递归的四条基本法则

1.基准情形。必须有某些基准情形,它无需递归就能解出。
2.不断推进。对于那些需要递归求解的情形,每一次递归调用都必须要使求解的状况朝接近基准情形的方向推进。
3.设计法则。假设所有的递归调用都能运行。
4.合成效益法则。在求解同一个问题的同一实例时,切勿在不同的递归调用中做重复性的工作

=[来源]: https://book.douban.com/subject/4924153/ "《数据结构与算法分析》Mark Allen Weiss著 机械工业出版社 "

一定不要试图跟踪大型递归的过程

要写出递归,关键就是找出递归的递归方程式: 也就是说,要完成最后一步,那么最后一步的前一步要做什么。

递推

所谓递归,即为对之前计算过的问题答案进行一些计算以获得当前问题的答案

相对于递归算法,递推算法免除了数据进出栈的过程,也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值.

分类

  • 顺推:从条件推出结果。

  • 逆推:从结果推出条件。

例题

用$1\times 2$ 的骨牌填满$2\times n$ 的矩形有多少种方案?

很容易发现当n是奇数时,结果是0。(面积法:3*n是一个奇数,奇数不可能由多个偶数1*2相加得到)

当n是偶数时,我们将3*n的区域用一条竖线分割成左右两个区域,右边区域记为3*k(2<=k<=n-2),而且右边区域不能被竖线分割成两个区域。
记右边区域的排列数为g(k),那么总的排列总数为g(k)*f(n-k)。当k=2时,我们通过画图可以发现g(2)=3;当k>2时,通过画图可以发现g(k)恒等于2.(因为右边区域不可被竖线分割,当右边区域的最右边的那一列由一 个1*2的格子和2*1的格子铺好时,剩余区域的铺法都唯一确定了,而1*2和2*1的格子位置可以上下互换,故恒等于2)
还有k=0的情况,也就是整个区域都不可以被竖线分割,那么铺法为2.
因此我们可以发现一个规律:
f(n)=3*f(n-2)+2*f(n-4)+2*f(n-6)+……+2*f(2)+2;
同理,f(n-2)=3*f(n-4)+2*f(n-6)+…..+2*f(2)+2;
两式相减可得 f(n)=4*f(n-2)-f(n-4)。

=[来源]: https://blog.csdn.net/weixin_42172676/article/details/81413611 "算法笔记(一)——Tri Tiling递推思路(杭电1143)"

经典例题

汉诺塔

抽象为数学问题
如下图所示,从左到右有A、B、C三根柱子,其中A柱子上面有从小叠到大的n个圆盘,现要求将A柱子上的圆盘移到C柱子上去,期间只有一个原则:一次只能移到一个盘子且大盘子不能在小盘子上面,求移动的步骤和移动的次数

《递归与递推 —— 跟WilliamYan一起学算法》

解:
(1) n == 1

​ 第1次 1号盘 A—->C sum = 1 次

(2) n == 2

​ 第1次 1号盘 A—->B
​ 第2次 2号盘 A—->C
​ 第3次 1号盘 B—->C sum = 3 次

(3)n == 3

​ 第1次 1号盘 A—->C
​ 第2次 2号盘 A—->B
​ 第3次 1号盘 C—->B
​ 第4次 3号盘 A—->C
​ 第5次 1号盘 B—->A
​ 第6次 2号盘 B—->C
​ 第7次 1号盘 A—->C sum = 7 次

不难发现规律:

​ 1个圆盘的次数 2的1次方减1
​ 2个圆盘的次数 2的2次方减1
​ 3个圆盘的次数 2的3次方减1
​ ……………………
​ n个圆盘的次数 2的n次方减1

故:移动次数为:$2^n – 1$

我们在利用计算机求汉诺塔问题时,必不可少的一步是对整个实现求解进行算法分析。

实现这个算法可以简单分为三个步骤:

  1. 把n-1个盘子由A 移到 B;
  2. 把第n个盘子由 A移到 C;
  3. 把n-1个盘子由B 移到 C;

从这里入手,在加上上面数学问题解法的分析,我们不难发现,移到的步数必定为奇数步:

  1. 中间的一步是把最大的一个盘子由A移到C上去;

  2. 中间一步之上可以看成把A上n-1个盘子通过借助辅助塔(C塔)移到了B上,

  3. 中间一步之下可以看成把B上n-1个盘子通过借助辅助塔(A塔)移到了C上;

=[参考]: https://dmego.me/2016/10/16/hanoi.html "汉诺塔的图解递归算法"

总结

今天的教程好像的确短了点呢……因为这实在是较为基础的部分了。递归和递推并不是某两种具体的算法,而仅仅是用来实现算法的两种方法。各位可以在看完本文后自行寻找适合的题目去做,这样才能提升自己的代码水平。

© 2019 WilliamYan
本文遵循CC-BY-SA共享协议。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据