總結（遞歸）

概述

什麼情況下用遞歸：大問題可以通過求解子問題求得，大問題與小問題有相同的特征

遞歸本質：通過自身調用自身縮小問題規模，邊界條件結束，回溯還原現場

以原問題為起點嘗試尋找把狀态空間（一個實際問題各種可能的情況構成的集合）縮小到已知的問題邊界的路線，再通過該路線返向回溯周遊的方式就是遞歸。

使用遞歸要求原問題與問題邊界之間的每個變換步驟具有相似性，即周遊的每個狀态都是相似的。即一個大問題可以轉化為一個又一個子問題求解。

遞歸是深度優先搜尋（DFS）的基礎。

執行操作：

1.縮小問題狀态空間的規模，程式嘗試尋找在原問題與問題邊界之間的變換路線，并向正在探索的路線上邁出一步

2.嘗試求解規模縮小以後的問題，結果可能是成功，也可能是失敗（自身調用自身）（由相同的程式求解）

3.如果成功，即找到了規模縮小後問題的答案，那麼将答案擴充到目前問題，如果失敗，那麼重新回到目前問題（回溯時還原現場），程式可能會繼續尋找目前問題的其他變換路線，直至最終确定目前問題無法求解。

遞歸實作指數型枚舉：

#include <bits/stdc++.h>
using namespace std;
const int SIZE=10005;
int a[SIZE],c[SIZE*10];
vector<int> chosen;
int n;
void calc(int x)
{
    cout<<"這算一次"<<endl;
    if(x==n+1)
    {
        for(int i=0;i<chosen.size();i++)
        {
            cout<<chosen[i];
        }
        puts("");
        return ;
    }

    calc(x+1);//求解子問題
    chosen.push_back(x);//選x，x被壓入chosen
    calc(x+1);//求解子問題
    chosen.pop_back();//準備回溯到上一問題之前，還原現場
}
int main()
{
    cin>>n;
    calc(1);
}

           

類似于深搜思想，一條路走到黑。我将代碼中的上界設為3，即求1到3所有的組合，包括該數本身。那麼該遞歸一開始就從頭走到尾，找到了3,并輸出出來，然後回溯還原現場即回到上一層狀态空間，剛剛的影響全部消失，以此類推。

遞歸實作組合型枚舉：

從1~n這n個整數中随機選出m個，輸出所有可能的選擇方案。

#include <bits/stdc++.h>
using namespace std;
const int SIZE=10005;
int a[SIZE],c[SIZE*10];
vector<int> chosen;
int n,m;
void calc(int x)
{
    if(chosen.size()>m||chosen.size()+(n-x+1)<m)//剪枝
        return;
    if(x==n+1)
    {
        for(int i=0;i<chosen.size();i++)
        {
            cout<<chosen[i];
        }
        puts("");
        return ;
    }
    calc(x+1);//求解子問題
    chosen.push_back(x);//選x，x被壓入chosen
    calc(x+1);//求解子問題
    chosen.pop_back();//準備回溯到上一問題之前，還原現場
}
int main()
{
    cin>>n>>m;
    calc(1);
}

           

遞歸實作排列型枚舉：

#include <bits/stdc++.h>
using namespace std;
const int SIZE=10005;
int a[SIZE],c[SIZE*10];
int n,m;
int order[20];
bool chosen[20];
void calc(int k)
{
    if(k==n+1)
    {
        for(int i=1;i<=n;i++)
        {
            cout<<order[i];
        }
        puts("");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(chosen[i]) continue;
        order[k]=i;
        chosen[i]=1;
        calc(k+1);
        chosen[i]=0;
        order[k]=0;
    }
}
int main()
{
    cin>>n;
    calc(1);
}