递归

递归是算法竞赛中的难点。传说人可以理解迭代，神理解递归。

To Iterate is Human, to Recurse, Divine. —L. Peter Deutsch

定义

直接或间接地出现对自身的调用。

本质

递归 = 递进 + 回归
(递进与回归缺一不可)

基本思想

把规模大的问题转化为规模小的相似的子问题来解决，且必须有一个明确的结束条件即递归出口

例1

求等差数列1，2，3，4，5，… …的第n项的值

(注：使用递归时需要写出递归表达式，而递归表达式 = 递归关系 + 递归出口)

代码如下：

#include <iostream>

using namespace std;

int f(int  n)
{
    if (n == 1) return 1;//递归出口
    else return f(n - 1) + 1;//递归关系:后一项等于前一项的值加1
}

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

同理，如果要求数列1，3，5，7，9，11… …中第n项的值，只需要把递归关系改为return f(n - 1) + 2;即可

递归过程如下所示：

例2 Fibonacci数列

1，1，2，3，5，8，13，21… …

#include <iostream>

using namespace std;

int f(int  n)
{
    if (n == 1 || n == 2) return 1;//递归出口
    else return f(n - 1) + f(n - 2);//递归关系
}

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

总结：利用递归完成的题目特点

• 可以将当前问题转换成规模更小的问题，且新问题和原问题解法完全相同
• 有一个明确的递归边界

例3 ：用递归方法求：1+2+3+……+n

(本题为中国矿业大学2021年考研初试题，很多同学以往用for循环完成本题，而疏于锻炼递归思想)

代码如下

#include <iostream>

using namespace std;

//Sum(n)表示数列前n项的和
int Sum(int  n)
{
    if (n == 1) return 1;//递归出口
    else return Sum(n - 1) + n;//递归关系
}

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

例4 ： 用递归方法求n!

#include <iostream>

using namespace std;

int f(int  n)
{
    if (n == 1) return 1;//递归出口
    else return f(n - 1) * n;//递归关系
}

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

例5 ： 王小二切饼

有一张大的煎饼在砧板上，饼不许离开砧板，切n（1<=n<=100)刀最多能将饼分成几块？

输入格式：输入切的刀数n

输出格式：输出切n刀最多切的块数

输入样例：3

输出样例：7

分析：
如图所示，切1刀最多可以将饼分成2块：

切2刀最多可以将饼分成4块：

切3刀最多可以将饼分成7块：

切4刀最多可以将饼分成11块：

不难发现：

• 要想将饼的块数切的较多，需要满足切割线两两相交且没有交点
• 第1刀 —— 2块；
• 第2刀 —— 4块；(2 + 2)
• 第3刀 —— 7块；(3 + 4)
• 第4刀 —— 11块；(4 + 7)
• … …
• 设第n-1刀 —— i块；
• 则第n刀 ——（n+i）块；

设切第n刀可以得到f(n)块饼，由此得到递归表达式：

if (n == 1) return 2;

else return f(n - 1) + n;

代码如下：

#include <iostream>

using namespace std;

int f(int  n)
{
    if (n == 1) return 2;//递归出口
    else return f(n - 1) + n;//递归关系
}

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