递归

在上一章中我们学习了自定义函数，知道可以在主函数中，或其它函数中调用自定义函数。但其实，不止不同函数之间可以相互调用，函数自己也可以调用自己。这个过程称之为递归。

递归的示例程序如下：

#include<iostream>
#include<cstdio>
using namespace std;
int f(int x)
{
    if(x==1||x==2) return 1;
    else return f(x-1)+f(x-2);
}
int main()
{
    int x;
    cin>>x;
    cout<<f(x);
    return 0;
}

可以看到，在函数f中又调用了函数f。函数f内部的运行可以解释为下述过程：

判断x是否与1相等或x是否与2相等，若是，则函数返回值为1
若1中的判断失败，则函数返回值为【参数为x-1的函数f的返回值】与【参数为x-2的函数f的返回值】之和。

如x=4，则调用过程如图所示：

                       f(4)

       f(3)                        f(2)

f(2)       f(1)                     1

1            1

也就是说，函数首先发现要计算f(4)，但此时x=4，不满足x与1相等或x与2相等，所以将f(4)展开为f(3)和f(2)，先计算f(3)和f(2)的值，再相加后，作为f(4)的返回值。

接下来根据从左往右执行的规则，函数要计算f(3)。计算f(3)的过程仍然与上述过程类似，展开为f(2)和f(1)后求和。

接下来求解由f(3)展开而得到的f(2)，发现符合x与2相等，因此f(2)返回1

求解由f(3)展开而得的的f(1)也同理返回1，因此f(3)=1+1=2，返回2

现在f(3)求解完成，再求解由f(4)展开的f(2)，得1，所以f(4)=f(3)+f(2)=2+1=3，因此f(4)最终返回值为3。

需要注意的是，在使用递归的时候，我们一定要给函数一个边界，让它不会在无限的自调用中迷失。该边界称为递归边界，没有边界的递归将如无限循环一般，必然造成超时。

以上就是斐波那契数列的递归过程。

但是在实际运行的时候我们发现，当求解斐波那契数列的项数较高的时候会卡在运行中很久，造成超时（TLE）。为什么呢？从上文我们对f(4)的分析就可以看出，f(2)被计算了2次。由此可以推断，当求解f(10)甚至f(100)的时候，会产生大量重复的计算过程，无意义地消耗了时间。此时，我们采用递归求解便不再合理，应该换用递推。

递推

在上文中，求斐波那契数列第n项，我们采用的是从f(n)开始，一层层向下展开。而根据斐波那契数列的特点，我们其实可以从第1项开始向上推，直到第n项。代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int x,f[1000];
    cin>>x;
	f[1]=1;
	f[2]=1;
	for(int i=3;i<=x;i++)
		f[i]=f[i-1]+f[i-2];
    cout<<f[x];
    return 0;
}

对于上述代码，求解f[4]的过程就变为如下描述：

已知x==1或x==2时，f[x]=1，所以初始化令f[1]=1,f[2]=1。
因为f[1]和f[2]都已经赋值，所以接下来从f[3]开始计算就可以。枚举f[3]~f[x]的每个单位，根据f[x]=f[x-1]+f[x-2]来求解。此处f[x]=f[x-1]+f[x-2]称为递推式。
求解完成，输出f[x]。

可以发现，递推求解是需要数组配合的。与递归不同的是，递推是采用空间换时间的做法，将每次求出来的f[x]保存下来，避免了重复求解，大大节约了时间。

以上，就是对递归和递推的基本描述。

第八章到此结束。

本章练习：

P1217 回文质数 Prime Palindromes

P1706 全排列问题