暴力递归

1，把问题转化为规模缩小了的同类问题的子问题
2，有明确的不需要继续进行递归的条件（base case）
3，有当得到了子问题的结果之后的决策过程
4，不记录每一个子问题的解

例1 用递归法求 $n！$

#include<bits/stdc++.h>
using namespace std;
long long ans;
long long fuck(long long n){
    if(n==1) return 1;
    return n*fuck(n-1);
}
int main(int argc, char const *argv[])
{
    long long n;
    scanf("%lld",&n);
    printf("%lld",fuck(n)); 
    return 0;
}

好的，现在我们由这道题转到上面暴力递归的定义

由定义1得到递推式 $F(n)=n*F(n-1)$
由定义2得到递归边界 $F(1)=1$
由定义3和1，2结论得到函数框架
由定义4得到 return n*fuck(n-1);

例2 汉诺塔问题

当前有三个柱子，第一根柱子为起始状态，现在要将第一根柱子上的碟子转移到第二根柱子
要求：
1，转移过程中包括末状态的任何时候，上面的碟子一定要比下面的碟子小
2，可以借用第三根柱子进行帮助
3，必须在最少的步骤内完成

图解

代码实践

#include<bits/stdc++.h>
using namespace std;
int tata(int n,string from,string to,string help){
    if(n == 1) cout << "Move " << n << ends << from << " to " << to <<endl;
    else{
        tata(n-1,from,help,to);
        cout << "Move " << n << ends << from << " to " << to <<endl;
        tata(n-1,help,to,from);

    }
}
int main(int argc, char const *argv[])
{
    tata(3,"a","b","c");
    return 0;
}

对应上面的定义，解释这个程序依然成立

例3 打印一个字符串的所有子序列

对于每一个字符串来说
我们只有两个状态，“要” or “不要” （缩小为子类同等问题）
根据状态，一直走到字符串的尾部程序结束（不再需要递归的条件）
每得到一个子问题的解就输出（得到子问题解之后的决策过程）

*图解

代码实践

#include<bits/stdc++.h>
using namespace std;
inline void chuan(string ch,int i,string res){
    if(i == ch.length()) {
        cout << res << endl;
        return;
    }
    chuan(ch,i+1,res+ch[i]);
    chuan(ch,i+1,res);
}

int main(int argc, char const *argv[])
{
    chuan("abc",0,"");
    return 0;
}