C++算法初级9——递归

递归，简单地来说，就是一个函数自己调用自己。

函数f()就好像是工厂中生产零件的模板，每次我们调用函数f()的时候，都会依照模板生产一个新的零件，名字叫“函数f()”。我们调用了很多次函数f()，也就是生产了很多名字相同的零件，它们的模样也相同，但是它们是不同的零件，因为我对一个零件操作不会影响到其他零件。

另外，两个函数相互调用也算是递归的一种，只要涉及到“函数自己调用自己”，都可以称为递归。

#include <bits/stdc++.h>
using namespace std;

void g();

void f() {
    g(); // f调用g
}

void g() {
    f(); // g调用f
}

int main() {
    f();
    return 0;
}

递归求阶乘

输入非负整数n，使用递归法求出n的阶乘，答案对998244353取模。

我们设f(n)为n的阶乘，那么根据阶乘的定义，我们可以得到：

f(0) = 1 // 初始值
f(n) = f(n-1) * n // 递归公式

//递归求阶乘
# include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int fac(int n)
{
    if(n==1)
        return 1;
    else
        return (long long)f(n-1) * n % MOD; 
}

int main()
{
    int n;
    cin>>n;
    cout<<fac(n)<<endl;
    return 0;
}

容易发现，递归的执行过程是“从上到下，再回到上”：

我们最开始是想知道f(5)的答案，但是想要知道f(5)就必须知道f(4)
想要知道f(4)就必须知道f(3)
……如此刨根问底，最后到了f(0)
我们直接得到了答案，然后再一层一层地返回，逐渐融合成我们想要的答案

因此，我们也可以分析出，该算法的时间复杂度是O(n)：“从上到下”的过程是O(n)，“再回到上”的过程也是O(n)，加起来一共是O(n)。

递归求斐波那契数列

输入正整数n，使用递归法求出斐波那契数列的第n项，答案对998244353取模

//递归求斐波那契数列
# include<bits/stdc++.h>
using namespace std;
//输入正整数n，使用递归法求出斐波那契数列的第n项，答案对998244353取模
const int mod=998244353;
int fib(int n)
{
    if(n==1||n==2)
        return 1;
    else
        return (fib(n-1)+fib(n-2))%mod;
}

int main()
{
    int n;
    cin>>n;
    cout<<fib(n)<<endl;
    return 0;
}

从归纳的角度思考递归
对于任意的递归函数，我们都可以从数学归纳法的角度去理解它，再抽象一点，就是：

1. 这个函数设计出来的目的是什么？

求斐波那契数列。

2. 在边界条件上，这个函数正确吗？

正确。

3. 这个函数能正确利用递归处理出来的结果吗？

可以正确使用。

因此这个函数是正确的。

第一点尤为重要！在理解一个递归函数之前，我们必须知道这个函数的目的是要干什么，这样才能使用数学归纳法。

这也警示我们，在写递归函数的时候，

不要让一个函数干两件事情！

不要让一个函数干两件事情！

不要让一个函数干两件事情！

只有每个函数干唯一指定的事情，才能保证写出来的代码是可靠易读易修改的。

第二点是我们大家都能想到的点，但是经常会忘记一些特殊情况导致漏写边界条件。在结果出问题的时候，需要检查一下是不是有什么边界条件忘记了。

第三点是递归最难理解的地方，这里分享一个小窍门：

在一个函数递归调用自己的时候，我们可以直接假设这个函数是一个已经写完，并且功能完善的函数，它能保质保量地完成我们想让它做的事情（这其实就是数学归纳法的前提假设）。

千万不要把递归函数展开，千万不要尝试研究递归的过程是什么样的，因为人脑根本无法承受如此大的数据量，我们只能用数学归纳法来保证递归函数的正确性。

同时，这也是为什么我们要求在写函数之前想好这个函数的任务，并且在写函数的过程中，这个任务始终不能变化，因为这是我们使用数学归纳法的前提，我们需要假设这个函数能完美地完成这个任务，才可以肆无忌惮地放心递归调用它。

那么，函数的正确性我们已经理解了，复杂度如何分析呢？

由于递归函数总是在边界条件处结束，因此我们可以重点关注边界条件被执行的次数，粗略地估计算法的复杂度。

比如求斐波那契数列的算法:

边界条件if( n == 1 || n == 2 ) return 1;执行的次数，其实就等于这个斐波那契数本身（这个数是由这样的1累计起来的），比如计算f(10)的复杂度就至少是O(f(10))，计算f(n)的复杂度就至少是O(f(n))，我们可以粗略地将这个算法的复杂度估计为“指数级”（因为斐波那契数本身的增长速度就是指数级）。这就足够了。

上面讲了如何理解一个递归算法，那么我们如何自己用递归算法解决问题呢？

仍然是牢记这三板斧：

确认并牢记这个递归函数的功能，始终不能改。
仔细检查，写对边界条件。
递归调用自己时，放心大胆地用，假设这个函数就是对的。

汉诺塔

汉诺塔
左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间需要遵循以下原则：

一次只能移到一个盘子且大盘子不能在小盘子上面，请你找出最少的移动步骤并换行打印出来。若将A最上面的盘子移动到B上，则可表示为 “A -> B”。

输入描述：

一行，一个整数n (n <= 20)。

输出描述：

若干行，每行代表一次操作。

比如：

A -> B

示例 1：
输入：
2
输出：
A -> B
A -> C
B -> C

//汉诺塔
# include "bits/stdc++.h"
using namespace std;

/*请你找出最少的移动步骤并换行打印出来。.
若将A最上面的盘子移动到B上，则可表示为 "A -> B"。

示例 1：
输入：
2
输出：
A -> B
A -> C
B -> C
*/
void hnt(int n, char start, char mid, char end)
{
    if(n==1)
    {
        cout << start << " -> " << end << endl;
    }
    else
    {
        hnt(n-1, start, end, mid); //将n-1个盘子从start移动到mid
        cout << start << " -> " << end << endl; //将第n个盘子从start移动到end
        hnt(n-1, mid, start, end); //将n-1个盘子从mid移动到end
    }
}
int main()
{
    int n;
    cin >> n;
    hnt(n, 'A', 'B', 'C');
    return 0;
}