6.递归阶乘思想

1. 阶乘

<mark>递归的逻辑中一般有两个重要概念：
①递归边界。
②递归式（或称递归调用）。
来看一个经典的例子：使用递归求解n的阶乘。</mark>
首先给出n！的计算式：n！=12…*n，这个式子写成递推的形式就是n！=（n-1）！*n，于是就把规模为n的问题转换为求解规模为n-1的问题。如果用F（n）表示n！，就可以写成F（n）=F（n-1）*n（即递归式），这样规模就变小了。
那么，如果把F（n）变为F（n-1），又把F（n-1）变为F（n-2），这样一直减小规模，什么时候是尽头呢？由于0！=1，因此不妨以F（O）=1作为递归边界，即当规模减小至n=0的时候开始“回头”。

#include <bits/stdc++.h>
using namespace std;
int F(int n)
{
	if(n==0) return 1;  //n=0 就是跳出递归的出口
	else return F(n-1)*n;
}
int main()
{
	int n;
	cout<<"请输入N："; 
	cin>>n;
	cout<<F(n);
	return 0;
}

2.斐波那契第n项

再来看另一个经典例子：求Fibonacci数列的第n项。
Fibonacci数列（即斐波那契数列）是满足F（O）=1，F（1）=1，F（n）=F（n-1）+F（n-2）（n>
2）的数列，数列的前几项为1，1，2，3，5，8，13，21…。由于从定义中已经可以获知递归边界为F（O）=1和F（1）=1，且递归式为F（n）=F（n-1）+F（n-2）（n≥2），因此可以仿照求解n的阶乘的写法，写出求解Fibonacci数列第n项的程序：

#include <bits/stdc++.h>
using namespace std;
int F(int n)
{
	if(n==1) return 1;
	else if(n==2) return 1;
	else return F(n-1)+F(n-2);
}
int main()
{
	int n;
	cout<<"请输入N："; 
	cin>>n;
	cout<<F(n);
	return 0;
}

TIP: 全排列 和 5皇后问题 待解决 [ 暂时跳过 ] 1.14