简单递归——斐不那契数列（C++）

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

int f(int n)

{

    if(n==1) return 0;

    if(n==2) return 1;

    return f(n-1) + f(n-2);

}

int main()

{

    int n;

    scanf("%d",&n);  //输入一个n

    printf("%d",f(n));

    return 0;          //返回一个斐不那契数列

}

递归实现指数型枚举

题目：从 1∼n1 这 n个整数中随机选取任意多个，输出所有可能的选择方案（依次考虑每个数选或者不选）

#include<iostream>

#include<cstdio>

using namespace std;

const int N = 15;

int n;

int s[N];  // 用来记录每个点的状态： 0 表示待考虑，1 表示选择该数， 2 表示不选

void dfs(int x) {

    if (x == n) {

        for (int i = 0; i <= n; i++) {

            if (s[i] == 1) {

                printf("%d ", i + 1);

            }

        }

        printf("\n");

        return;

    }

    s[x] = 2;

    dfs(x + 1);  // 第一个分支，不选

    s[x] = 0;    // 恢复现场

    s[x] = 1;

    dfs(x + 1);  // 第二个分支，选

    s[x] = 0;

}

int main() {

    cin >> n;

    dfs(0); // 从第一个开始遍历

    return 0;

}