算法笔记(1)——递归的理论及其应用_线性递归理论的应用

前言

在经历了一些编程比赛和实际项目运用后，开始逐渐感受到算法的魅力与美丽。个人认为要想写出出色的程序并基于此做其他事，学习掌握算法还是很有必要的。这个专栏来源于早期编程比赛的笔记，主要用于总结一些基础算法的理论和应用，在后续的学习过程中将持续更新此专栏。

算法笔记(1)——递归

作者在写本篇文章时主要参考了以下资料：
https://chenqx.github.io/2014/09/29/Algorithm-Recursive-Programming
https://mp.weixin.qq.com/s/mJ_jZZoak7uhItNgnfmZvQ
https://blog.csdn.net/duan19920101/article/details/51252577

To iterate is human,to recurse divine.—— L. Peter Deutsch

迭代是人，递归是神

​ 递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法的实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解。

​ 它表现在一段程序中往往会遇到调用自身的那样一种coding策略，这样我们就可以利用大道至简的思想，把一个大的复杂的问题层层转换为一个小的和原问题相似的问题来求解的这样一种策略。递归往往能给我们带来非常简洁非常直观的代码形势，从而使我们的编码大大简化，然而递归的思维确实很我们的常规思维相逆的，我们通常都是从上而下的思维问题， 而递归趋势从下往上的进行思维。这样我们就能看到我们会用很少的语句解决了非常大的问题，所以递归策略的最主要体现就是小的代码量解决了非常复杂的问题。

实质：自己调用自己

1. 递归三大要素

1.1 递归的功能——这个函数要干嘛？

​ 定义递归函数

1.2 递归出口——函数的终止条件

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

1.3 递归循环——找出函数的等价表达式

​ 我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。

2. 循环与递归

3. 尾递归

对于递归函数的使用，人们所关心的一个问题是栈空间的增长。确实，随着被调用次数的增加，某些种类的递归函数会线性地增加栈空间的使用 —— 不过，有一类函数，即尾部递归函数，不管递归有多深，栈的大小都保持不变。尾递归属于线性递归，更准确的说是线性递归的子集。
　　函数所做的最后一件事情是一个函数调用（递归的或者非递归的），这被称为 尾部调用（tail-call）。使用尾部调用的递归称为 尾部递归。当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
　　让我们来看一些尾部调用和非尾部调用函数示例，以了解尾部调用的含义到底是什么：

int test1(){
    int a = 3;
    test1(); /* recursive, but not a tail call.  We continue */
             /* processing in the function after it returns. */
    a = a + 4;
    return a;
}
int test2(){
    int q = 4;
    q = q + 5;
    return q + test1(); /* test1() is not in tail position.
                         * There is still more work to be
                         * done after test1() returns (like
                         * adding q to the result*/
}
int test3(){
    int b = 5;
    b = b + 2;
    return test1();  /* This is a tail-call.  The return value
                      * of test1() is used as the return value
                      * for this function.*/                    
}
int test4(){
    test3(); /* not in tail position */
    test3(); /* not in tail position */
    return test3(); /* in tail position */
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

可见，要使调用成为真正的尾部调用，在尾部调用函数返回之前，对其结果 不能执行任何其他操作。
注意，由于在函数中不再做任何事情，那个函数的实际的栈结构也就不需要了。惟一的问题是，很多程序设计语言和编译器不知道 如何除去没有用的栈结构。如果我们能找到一个除去这些不需要的栈结构的方法，那么我们的尾部递归函数就可以在固定大小的栈中运行。
　　在尾部调用之后除去栈结构的方法称为 尾部调用优化 。
　　那么这种优化是什么？我们可以通过询问其他问题来回答那个问题：

(1) 函数在尾部被调用之后，还需要使用哪个本地变量？哪个也不需要。
(2) 会对返回的值进行什么处理？什么处理也没有。
(3) 传递到函数的哪个参数将会被使用？哪个都没有。
1
2
3

好像一旦控制权传递给了尾部调用的函数，栈中就再也没有有用的内容了。虽然还占据着空间，但函数的栈结构此时实际上已经没有用了，因此，尾部调用优化就是要在尾部进行函数调用时使用下一个栈结构 覆盖 当前的栈结构，同时保持原来的返回地址。
　　我们所做的本质上是对栈进行处理。再也不需要活动记录（activation record），所以我们将删掉它，并将尾部调用的函数重定向返回到调用我们的函数。 这意味着我们必须手工重新编写栈来仿造一个返回地址，以使得尾部调用的函数能直接返回到调用它的函数。

4. 关于递归的一些优化思路

4.1 考虑是否重复计算

​ 如果你使用递归的时候不进行优化，是有非常非常非常多的子问题被重复计算的。

啥是子问题？ f(n-1),f(n-2)….就是 f(n) 的子问题了。

例如对于[案例5.2](5.2 小青蛙跳台阶)那道题，f(n) = f(n-1) + f(n-2)。递归调用的状态图如下：

4.2 考虑是否可以自底向上

5. 案例

3.1 斐波那契数列

​ 斐波那契数列是这样一个数列：1、1、2、3、5、8、13、21、34….，即第一项 f(1) = 1,第二项 f(2) = 1……,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。

int f(int n){
    // 递归出口
	if(n<=2){   / if(n==1||n==2)
		return 1
	}
    // 递归循环
	return f(n-1)+f(n-2)
}
1
2
3
4
5
6
7
8

5.2 小青蛙跳台阶

​ 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

先找出递归出口：
直接把 n 压缩到很小很小就行了，因为 n 越小，我们就越容易直观着算出 f(n) 的多少，所以当 n = 1时，你知道 f(1) 为多少吧？够直观吧？即 f(1) = 1。

再找出递归循环：
每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。

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

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

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

int f(int n){
    if(n == 1){
        return 1;
    }
    ruturn f(n-1) + f(n-2);
}
1
2
3
4
5
6

上述代码出口有问题，修改如下：

int f(int n){
2    //f(0) = 0,f(1) = 1，等价于 n<=2时，f(n) = n。
3    if(n <= 2){
4        return n;
5    }
6    ruturn f(n-1) + f(n-2);
7}
1
2
3
4
5
6
7

3.3 汉诺塔问题

​ 古代有一个梵塔，塔内有 A、B、C 三个基座，A 座上有 64 个盘子，盘子大小不等，大的在下，小的在上。有人想把这 64 个盘子
从 A 座移到 C 座，但每次只允许移动一个盘子，并且在移动的过程中，3 个基座上的盘子始终保持大盘在下，小盘在上。在移动过程中
盘子可以放在任何一个基座上，不允许放在别处。编写程序，用户输入盘子的个数，显示移动的过程。

• 如果只有 1 个盘子，则不需要利用B塔，直接将盘子从A移动到C。

• 如果有 2 个盘子，可以先将盘子1上的盘子2移动到B；将盘子1移动到C；将盘子2移动到C。这说明了：可以借助B将2个盘子从A移动到C，当然，也可以借助C将2个盘子从A移动到B。

• 如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。

以此类推，上述的思路可以一直扩展到 n 个盘子的情况，将将较小的 n-1个盘子看做一个整体，也就是我们要求的子问题，以借助B塔为例，可以借助空塔B将盘子A上面的 n-1 个盘子从A移动到B；将A最大的盘子移动到C，A变成空塔；借助空塔A，将B塔上的 n-2 个盘子移动到A，将C最大的盘子移动到C，B变成空塔…
　　根据以上的分析，不难写出程序：

def Hanoi(n, ch1, ch2, ch3):
    if n == 1:
        print(ch1, '->', ch3)
    else:
        Hanoi(n - 1, ch1, ch3, ch2)
        print(ch1, '->', ch3)
        Hanoi(n - 1, ch2, ch1, ch3)
N = int(input("请输入盘子的数量："))
Hanoi(N, 'A', 'B', 'C')
1
2
3
4
5
6
7
8
9