思路

1. 找到大问题到小问题的转移过程：把大问题分解为多个相似的小问题
2. 找到最小问题的解决方案：解决边界问题
3. 合并小问题的解决，得到整个问题的解决方案

例题

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
long long func(int i){
    if (i==1){
        return 1;
    }else if (i==0){
        return 0;
    }
    return func(i-1)+func(i-2);
}
int main() {
    int i;
    while (scanf("%d",&i) != EOF){
        printf("%lld",func(i));
    }
    return 0;
}

代码模板

template func(int n//问题规模){
	if(n==边界){
		解决方案；
	}else{
		func(n-1);//分解问题
		//更多解决措施
	}
}

例题2

分析

• 递推公式：假设左子树和右子树结点数已知，那么树中结点总数量相当于左子树结点数+右子树结点数+1，这就是递归的公式。
• 边界条件：左/右孩子不存在
• 完全二叉树的结点序号：根的编号2为左孩子编号，根的编号2+1为右孩子编号

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
long long func(int m,int n){
    if (m>n){
        return 0;
    }else {
        return 1+func(2*m,n)+ func(2*m+1,n);
    }
}
int main() {
    int m,n;
    while (scanf("%d%d",&m,&n) != EOF){
        if (m==0){
            break;
        }
        printf("%lld",func(m,n));
    }
    return 0;
}