递归的几个例子

递归

1 数字划分：求将数字分解为不同数字相加的种类

例如2=2 、2=1+1 两种 3=3， 3=2+1，3=1+1+1 三种

int split(int n, int max){
    if(n == 0 || max == 1)
        return 1;
    if(max > n)
        return split(n, n);
    return split(n-max, max) + split(n, max - 1);
}

将不同的种类都输出

#include "iostream"
#include "vector"
using namespace std;

int N;
void split(int n, int max, vector<int> &pre){
    if(n == 0){
        cout << N << '=';
        for(int i = 0;i < pre.size() - 1; i++) cout << pre[i] << '+';
        cout << pre.back() << endl;
        return;
    }
    if(max == 1){
        cout << N << '=';
        for(int i = 0;i < pre.size(); i++) cout << pre[i] << '+';
        for(int i = 0;i < n - 1; i++) cout << 1 << '+';
        cout << 1 << endl;
        return;
    }
    if(max > n) {
        split(n, n, pre);
        return;
    }
    pre.push_back(max);
    split(n-max, max, pre);
    pre.pop_back();
    split(n, max - 1, pre);
}

int main(){
    N = 10;
    vector<int> pre;
    split(N, N, pre);
}

结果

10=10
10=9+1
10=8+2
10=8+1+1
10=7+3
10=7+2+1
10=7+1+1+1
10=6+4
10=6+3+1
10=6+2+2
10=6+2+1+1
10=6+1+1+1+1
10=5+5
10=5+4+1
10=5+3+2
10=5+3+1+1
10=5+2+2+1
10=5+2+1+1+1
10=5+1+1+1+1+1
10=4+4+2
10=4+4+1+1
10=4+3+3
10=4+3+2+1
10=4+3+1+1+1
10=4+2+2+2
10=4+2+2+1+1
10=4+2+1+1+1+1
10=4+1+1+1+1+1+1
10=3+3+3+1
10=3+3+2+2
10=3+3+2+1+1
10=3+3+1+1+1+1
10=3+2+2+2+1
10=3+2+2+1+1+1
10=3+2+1+1+1+1+1
10=3+1+1+1+1+1+1+1
10=2+2+2+2+2
10=2+2+2+2+1+1
10=2+2+2+1+1+1+1
10=2+2+1+1+1+1+1+1
10=2+1+1+1+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

2 全排列

#include "iostream"
#include "vector"
using namespace std;

const int N = 10;
int a[N] = {1,2,3,4,5};
int m = 4;

void arrangement(int n){
    if(n == m - 1){
        for(int i = 0;i < m; i++) cout << a[i] << ' ';
        cout << endl;
        return;
    }

    for(int i = n; i<m;i++){
        swap(a[i], a[n]);
        arrangement(n+1);
        swap(a[i], a[n]);
    }

}

int main(){
    arrangement(0);
}

结果

1 2 3 4 
1 2 4 3 
1 3 2 4 
1 3 4 2 
1 4 3 2 
1 4 2 3 
2 1 3 4 
2 1 4 3 
2 3 1 4 
2 3 4 1 
2 4 3 1 
2 4 1 3 
3 2 1 4 
3 2 4 1 
3 1 2 4 
3 1 4 2 
3 4 1 2 
3 4 2 1 
4 2 3 1 
4 2 1 3 
4 3 2 1 
4 3 1 2 
4 1 3 2 
4 1 2 3 

组合数

const int N = 5;
int a[N] = {1, 2, 3, 4, 5};
int m = 3;

void combination(vector<int> &res, int n) { // C(N, m)
    if (m - res.size() > N - n) return;
    if (m - res.size() == N - n) {
        for (int i = 0; i < res.size(); i++) cout << res[i] << ' ';
        for (int i = n; i < N; i++) cout << a[i] << ' ';
        cout << endl;
        return;
    }
    res.push_back(a[n]);
    combination(res, n + 1);
    res.pop_back();
    combination(res, n + 1);
}

int main() {
    vector<int> res;
    combination(res, 0);
}

结果

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

汉诺塔

void hanoi(int from, int temp, int to, int n){
    if(n == 1){
        cout << from << "->" << to << endl;
        return;
    }

    hanoi(from, to, temp, n-1);
    cout << from << "->" << to << endl;
    hanoi(temp, from, to, n-1);
}

int main() {
    hanoi(1, 2, 3, 3);
}

结果

1->3
1->2
3->2
1->3
2->1
2->3
1->3