递归函数

什么是递归？

玄而由玄！

递归函数是一个可以自己调用自己的函数！

斐波那契数列：$\tt f(n)=f(n-1)+f(n-2)$

递归是一门甩锅的艺术:

何老师有一天问了某位同学x斐波那契数列第五项是多少？ 这位x同学非常善于巧妙的甩锅(超级懒）,于是找来y和z问他们f(4)和f(3).y和z也不笨继续问别人，直到问到f(1)和f(2).

int f(int n) 
{
     if (n==1||n==2) return 1;
     return f(n-1)+f(n-2);
}

递归事实上是很慢！问题在于同一个问题重复问。以斐波那契数列算$\tt f(5)$,$\tt f(3)$被重复询问了两次。所以递归的问题在于重复计算！

解决重复计算方法就是记忆化！

什么是记忆化？就是用空间来换时间，记录所有中间解的答案，当重复问一个之前已经得到答案的问题，直接返回其答案，保证同一个问题只问一次。

int F[50];
int f(int n) {
     if (F[n]) return F[n];
     if (n==1||n==2) return 1;
     return F[n]=f(n-1)+f(n-2); 
}

求组合数

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

 
int C(int n,int m) {
	if (m==0) return 1;
	if (n<m)  return 0;
	if (n==m) return 1;
	return C(n-1,m)+C(n-1,m-1);
} 

int main() {
	cout<<C(5,2)<<' '<<C(5,3)<<endl;
	return 0;
}

递归解决不会回到同一个点的路径问题

比如说：只能向右或者向下的问题。

过河卒：

#include<bits/stdc++.h>
#define int long long
using namespace std;
bool a[21][21];
int f[21][21];
int dx[]={-1,-2,-2,-1,1,2,2,1};
int dy[]={-2,-1,1,2,2,1,-1,-2};
int F(int n,int m) {
	if (~f[n][m]) return f[n][m];
	if (a[n][m]) return 0;
	if (n == 0&& m == 0) return 1;
	int res = 0;
	if (n>0) res=F(n-1,m);
	if (m>0) res+=F(n,m-1);
	return f[n][m]=res;
}
signed main() {
	memset(f,-1,sizeof(f));
	int n,m,x,y;
	cin>>n>>m>>x>>y;a[x][y]=true;//被占用
	for (int i = 0 ; i < 8 ; i ++ ) {//马一步可以走到的位置 
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx<0||nx>n||ny<0||ny>m) continue;
		a[nx][ny]=true;//地图内部点 
	} 
	cout<<F(n,m)<<endl; 
	return 0;
}

深度优先搜索是递归的两个套路！

路径问题

所有关于起点到终点的问题！

递归模板是：

void DFS(当前点坐标) {

     if (当前点==终点) {
           return ;
     }
     枚举当前能够一步到达所有点(nx,ny)
         if ((nx,ny)合法） {
              标记(nx,ny）
              DFS（nx,ny)
              撤销标记(nx,ny)
         }
}

应用：数字三角形

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


bool vis[1001][1001];
int a[1001][1001];
int f[1001][1001];
int n,ans;
//(1,1)->(x,y)->(n,i)
void DFS(int x,int y,int sum) {
//	cout<<x<<' '<<y<<' '<<sum<<endl;
	if (f[x][y]>=sum) return ;
	f[x][y]=sum;
	if (x==n) {
		ans = max(ans,sum);
		return ;
	}
	//x,y->x+1,y,x+1,y+1
	for (int i = 0 ; i <= 1; i ++ ) {
		if (vis[x][y+i]) continue;
		vis[x][y+i]=true;
		DFS(x+1,y+i,sum+a[x+1][y+i]);//当前这个函数会等待 
		vis[x][y+i]=false; 
	}
} 
int main() {
	cin>>n;
	for (int i = 1; i <= n ; i ++ ) 
	    for (int j= 1; j <= i ; j ++ )  cin>>a[i][j];
	DFS(1,1,ans=a[1][1]);
	cout<<ans<<endl; 
	return 0;
}

填数问题

模板：

DFS(当前所填数的下标）
{
    if (如果填完所有的数） {
         return ;
    }
   for (枚举所有可能的填的数) {
        填上去;标记所填;
       DFS(下一个位置);
        撤销标记;
    }
}