[TOC]
暴力遞歸
1，把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題
2，有明確的不需要繼續(xù)進(jìn)行遞歸的條件（base case）
3坡锡，有當(dāng)?shù)玫搅俗訂栴}的結(jié)果之后的決策過程
4蓬网，不記錄每一個子問題的解
例1 用遞歸法求 
#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;
}
好的鹉勒，現(xiàn)在我們由這道題轉(zhuǎn)到上面暴力遞歸的定義
- 由定義1得到遞推式
- 由定義2得到遞歸邊界
- 由定義3和1帆锋，2結(jié)論得到函數(shù)框架
- 由定義4得到
return n*fuck(n-1);
例2 漢諾塔問題
當(dāng)前有三個柱子，第一根柱子為起始狀態(tài)贸弥，現(xiàn)在要將第一根柱子上的碟子轉(zhuǎn)移到第二根柱子
要求：
1窟坐，轉(zhuǎn)移過程中包括末狀態(tài)的任何時候，上面的碟子一定要比下面的碟子小
2绵疲，可以借用第三根柱子進(jìn)行幫助
3哲鸳，必須在最少的步驟內(nèi)完成
- 圖解
- 代碼實(shí)踐
#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;
}
- 對應(yīng)上面的定義，解釋這個程序依然成立
例3 打印一個字符串的所有子序列
對于每一個字符串來說
我們只有兩個狀態(tài)盔憨，“要” or “不要” （縮小為子類同等問題）
根據(jù)狀態(tài)徙菠，一直走到字符串的尾部程序結(jié)束 （不再需要遞歸的條件）
每得到一個子問題的解就輸出 （得到子問題解之后的決策過程）
*圖解
- 代碼實(shí)踐
#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;
}
