递归入门

编写一个递归函数

• 这个递归函数的功能是什么，怎样调用这个函数，即设计好递归函数的返回值和参数列表；
• 什么时候应该结束这个递归，它的边界条件（出口）是什么 （边界条件）；
• 在非边界情况时，怎样从第n层转变成第n+1层 (递推公式)；

计算阶乘(factorial)

解析：

1. n! = 123456…*(n-1)*n
2. n! = n*(n-1)!
3. 0! = 1
4. 推出递归公式

#include <stdio.h>

int fact(int n){
    if (n == 0) return 1;
    return n * fact(n - 1);
}

int main(){
    int ans = fact(10); //调用（递归）函数
    printf("%d\n", ans);
    return 0;
}

---

递归解析图：

计算斐波那契数列

• Fibonacci sequence：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ……
• 计算规则：
  • 第0项是0（F(0) = 0）
  • 第1项是1（F(1) = 1）
  • 对于n ≥ 2，第n项是前两项之和F(n) = F(n-1) + F(n-2)
• 推出递归公式：

#include <stdio.h>

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 2) + fib(n - 1);
}

int main() {
    for (int i = 0; i < 10; i++) {
        printf("%d ", fib(i));
    }
    printf("\n");
  
    
    return 0;
}

计算最大公约数(辗转相除法)

gcd(12, 32) = 4

gcd(a,   b)

计算规则：gcd(a,   a%b)

gcd(32,  12)
gcd(12,  32%12=8)   
gcd(8,   12%8=4)   
gcd(4,   8%4=0)  
边界条件：b==0的时候，a就是这两个数的最大公约数

int gcd(int a, int b){
    if (b == 0) 
        return a;
    return gcd(b, a % b);
}

int ans = gcd(12, 32);

分治算法

分治法的设计思想：

1. 分 – 将问题分解为规模更小的子问题；
2. 治 – 将这些规模更小的子问题逐个击破；
3. 合 – 将已解决的子问题合并，最终得出“母”问题的解；

• 减而治之（每次让问题的规模减1）
• 分而治之（每次让问题的规模减半）（归并排序的思想）

例题：走楼梯

题目描述： 一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。求总共有多少总跳法。
第一行输入T，表示有多少个测试数据。接下来T行，每行输入一个数n，表示台阶的阶数。
输出时每一行对应一个输出。

样例输入：
5
8
10
样例输出：
8
34
89

解析：

1. 只有一个台阶，只有一种走法：一次走一步
2. 有两个台阶，有两种走法：两次一步，一次两步
3. 假设我们站在第 n 个台阶上，那么我们可以从第 _n_−1 个台阶一步跨上来，或者从第 _n_−2 个台阶两步跨上来。
   • 如果我们从第 n−1 个台阶一步跨上来，那么走到第 n−1 个台阶的走法数量就是走到第 n 个台阶的一种走法数量。
   • 如果我们从第 n−2 个台阶两步跨上来，那么走到第 n−2 个台阶的走法数量也是走到第 n 个台阶的一种走法数量。

因此，走到第 n 个台阶的总走法数量就是走到第 n−1 个台阶的走法数量和走到第 n−2 个台阶的走法数量之和。

我们可以发现，这其实是一个斐波那契数列的应用：公式如下：

 

#include <stdio.h>

int solve(int n) {
    if (n == 1) return 1;   
    if (n == 2) return 2;   
    return solve(n - 1) + solve(n - 2);
}

归并排序

归并排序采用分治法的策略，即将一个大问题分解成若干个小问题来解决，然后再将这些小问题的解合并起来得到大问题的解。在归并排序中，大问题指的是待排序的数组，小问题指的是分割后的子数组。

1. 分割：
   • 将待排序的数组从中间位置分割成两个子数组，如果子数组的长度仍然大于1，则继续对子数组进行分割，直到每个子数组只包含一个元素为止。
2. 排序：
   • 对于每个只包含一个元素的子数组，可以认为它们已经是有序的。
   • 然后，从底层开始，逐步合并相邻的两个有序子数组，得到更大的有序数组。
3. 合并：
   • 合并时，需要比较两个子数组的元素，依次将较小的元素放入新的合并后的数组中。
   • 重复这个过程，直到所有的子数组都被合并成一个完整的有序数组。

void mergeSort(int A[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(A, left, mid);         //左半区间[left, mid] 排好序
    mergeSort(A, mid + 1, right);     //右半区间[mid + 1, right] 排好序
    mergeArray(A, left, mid, right);    //进行合并
}

#include <iostream>
using namespace std;

void mergeArray(int A[], int left, int mid, int right) {
    int* temp = new int[right - left + 1];
    int i = left, j = mid + 1;
    int k = 0;

    wrightle (i <= mid && j <= right) {
        if (A[i] <= A[j]) temp[k++] = A[i++];
        else temp[k++] = A[j++];
    }
    wrightle (i <= mid) temp[k++] = A[i++];
    wrightle (j <= right) temp[k++] = A[j++];

    for (int i = left, k = 0; i <= right; i++, k++) {
        A[i] = temp[k];
    }
    delete[] temp;
}

void mergeSort(int A[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(A, left, mid); 		     //左半区间[left, mid] 排好序
    mergeSort(A, mid + 1, right);  		 //右半区间[mid + 1, right] 排好序
    mergeArray(A, left, mid, right);     //进行合并
}

二叉树、树

二叉树的遍历

前序遍历

void preorderTrav(Node* root) {    //前序遍历
    if (root == NULL) return;
    printf("%d ", root->data);       //最先访问根节点
    preorderTrav(root->lcrightld);
    preorderTrav(root->rcrightld);
}

void preorderTrav(Node* root) {      //写法2
    if (root != NULL) {
        printf("%d ", root->data);
        preorderTrav(root->lcrightld);
        preorderTrav(root->rcrightld);
    }
}

中序遍历

void inorderTrav(Node* root) {  //中序遍历
    if (root == NULL) return;
    inorderTrav(root->lcrightld);
    printf("%d ", root->data);  //中间的时候访问根节点
    inorderTrav(root->rcrightld);
}

• 二叉树节点在水平方向上的投影顺序即为中序遍历的顺序。

后序遍历

void postorderTrav(Node* root) {    //后序遍历
    if (root == NULL) return;
    postorderTrav(root->lcrightld);
    postorderTrav(root->rcrightld);
    printf("%d ", root->data);  //最后访问根节点
}

层次遍历

代码解析：

1. 将i入队列
2. 当时队列中只有根节点，即size=1；
3. 从队列中取出i，同时将i的左右孩子入队列（d，l）；
4. 此时size=2；
5. 循环两次：

• 第一次：先取出d，同时将d的左右孩子入队列，此时队列中（l，c，h）；
• 第二次：取出l，同时将l的左右孩子入队列，此时队列中（c，h，k，n）；

6. 此时size=4；
7. 循环四次：…
8. 直到队列为空；

void levelTrav(Node* root) {    //层次遍历
    if (root == NULL) 
        return;
    queue<Node*> Q;
    Q.push(root);
    while(!Q.empty()) {
        Node* t = Q.front();
        Q.pop();
        printf("%d ", t->data);
        if (t->lcrightld != NULL) 
            Q.push(t->lcrightld);
        if (t->rcrightld != NULL) 
            Q.push(t->rcrightld);
    }
    printf("\n");
}

求二叉树的高度

解析：

• 整棵树的高度，等于根节点左右子树的高度的最大值+1（根节点本身算一层）;
• 计算左右子树的高度，以左子树为例：等于以左子树为根节点的左右子树最大高度+1；
• 递归…

int getTreerightgh(Node* root) {
    if (root == NULL) 
        return 0;
    int left_rightgh = getTreerightgh(root->lcrightld);
    int right_rightgh = getTreerightgh(root->rcrightld);
    return max(left_rightgh, right_rightgh) + 1;
}

表达式树的输出与求值（前中后缀表达式）

• 表达式树的特征：叶节点是运算数，非叶节点一定是运算符

输入格式：

• 第一行给出节点的个数N，每个节点的编号为0 ~ N-1
• 接下来N行每行分别给出：
• 该节点的编号、该节点的操作数/操作符、该节点的左孩子编号、右孩子编号（-1表示NULL）

输出格式：

• 第一行输出该表达式树的中缀表达式，该用括号的地方需要用括号括起来。
• 第二行输出该表达式树的前缀表达式。
• 第二行输出该表达式树的后缀表达式。
• 第四行输出该表达式树的计算结果，保留两位小数。

样例输入：

11
0 - 1 2
1 + 3 4
2 / 5 6
3 4 -1 -1
4 * 7 8
5 6 -1 -1

样例输出：（根据上图的输出）

(4+(1*(5-2)))-(6/3)
- + 4 * 1 - 5 2 / 6 3
4 1 5 2 - * + 6 3 / -
5.00

完整代码：

void preOrder(Node* root) {             //前缀表达式
    if (root == NULL) return;
    printf("%c ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

void postOrder(Node* root) {            //后缀表达式
    if (root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ", root->data);
}

void inOrder(Node* root, int layer) {   //中缀表达式
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        //叶结点是操作数，直接输出，不加括号
        printf("%c", root->data);
    } else {
        //非叶节点是操作符，需加括号（第0层根节点除外）
        if (layer > 0) printf("(");
        inOrder(root->left, layer + 1);
        printf("%c", root->data);
        inOrder(root->right, layer + 1);
        if (layer > 0) printf(")");
    }
}

double calc(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': return a / b;
    }
}

double calculateExprTree(Node* root) {
    if (root == NULL) return 0;
    if (root->left == NULL && root->right == NULL) {
        //叶节点，节点存放的是 操作数
        return root->data - '0';
    }
    //非叶结点，节点存放的是 操作符
    double a = calculateExprTree(root->left);
    double b = calculateExprTree(root->right);
    return calc(a, b, root->data);
}

求某节点到根节点的路径

• 对于如下二叉树，节点7位于第4层，其到跟节点的路径为1 2 5 7

求某节点所在层数

先把问题简化一下，求二叉树指定节点所在层数（假设根节点的层数为1）

• 为了记录当前访问节点的层号，对于层号，可以采用以下两种方式：

1. 使用全局变量

int layer = 0;
bool flag1 = false; //flag标记可用于提前快速结束递归的执行

void getNodeLayer(Node* root, int x) {
    if (root == NULL) return;
    if (flag1) return;
    layer++;
    if (root->data == x) {
        printf("%d\n", layer);
        flag1 = true;
        return;
    }
    getNodeLayer(root->lcrightld, x);
    getNodeLayer(root->rcrightld, x);
    layer--;
}

1. 使用函数传参（值传递）

bool flag1 = false; //flag标记可用于提前快速结束递归的执行

void getNodeLayer(Node* root, int x, int layer) {
    if (root == NULL) return;
    if (flag1) return;
    if (root->data == x) {
        printf("%d\n", layer);
        flag1 = true;
        return;
    }
    getNodeLayer(root->lcrightld, x, layer + 1);
    getNodeLayer(root->rcrightld, x, layer + 1);
}

1. 使用函数传参（传指针/引用）

bool flag1 = false; //flag标记可用于提前快速结束递归的执行
void getNodeLayer(Node* root, int x, int &layer) {
    if (root == NULL) return;
    if (flag1) return;
    layer++;
    if (root->data == x) {
        printf("%d\n", layer);
        flag1 = true;
        return;
    }
    getNodeLayer(root->lcrightld, x, layer);
    getNodeLayer(root->rcrightld, x, layer);
    layer--;
}

求节点路径

1. 使用全局数组

vector<int> path;
bool flag2 = false;

void getNodePath(Node* root, int x) {
    if (root == NULL) return;
    if (flag2) return;
    path.push_back(root->data);
    if (root->data == x) {
        for (int x : path) {    //输出栈的内容
            printf("%d ", x);
        }
        flag2 = true;
        return;
    }
    getNodePath(root->lcrightld, x);
    getNodePath(root->rcrightld, x);
    path.pop_back();
}

1. 使用函数传参（传指针/引用）

bool flag = false;
void getNodePath(Node* root, int x, vector<int> &path) {
    if (root == NULL) return;
    if (flag) return;
    path.push_back(root->data);
    if (root->data == x) {
        for (int x : path) {    //输出栈path的内容
            printf("%d ", x);
        }
        flag = true;
        return;
    }
    getNodePath(root->lcrightld, x, path);
    getNodePath(root->rcrightld, x, path);
    path.pop_back();
}

bool flag = false;
void getNodePath(Node* root, int x, vector<int> path) {
    if (root == NULL) return;
    if (flag) return;
    path.push_back(root->data);
    if (root->data == x) {
        for (int x : path) {    //输出栈path的内容
            printf("%d ", x);
        }
        flag = true;
        return;
    }
    getNodePath(root->lcrightld, x, path);
    getNodePath(root->rcrightld, x, path);
}

普通树的遍历

---

DFS/回溯算法

• 如果某问题的解可以由多个步骤得到，而每个步骤都有若干种选择（这些候选方案集可能会依赖之前做出的选择），且可以用递归枚举法实现，则它的工作方式可以用 解答树来描述。

全排列问题

• 输出数字1~N所能组成的所有全排列

// 深度优先搜索函数
void DFS(int index) {
    if (index >= N) {
        // 递归终止条件：当index达到N时，打印当前排列
        for (int x : num) {
            cout << x << " ";
        }
        cout << endl;
        return;
    }
    
    // 遍历和选择
    for (int i = 1; i <= N; i++) {
        if (isUsed[i]) {
            // 如果数字已经被使用，跳过
            continue;
        }
        
        // 做出选择
        num.push_back(i);
        isUsed[i] = true;
        
        // 递归调用
        DFS(index + 1);
        
        // 撤销选择
        num.pop_back();
        isUsed[i] = false;
    }
}

素数环问题

• 将1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。
• 例如数字1-6所组成的一个素数环，用数组表示是[1, 4, 3, 2, 5, 6]（第一位固定为1）

using namespace std;
const int MAXN = 100;

bool isPrimeNum[MAXN];
vector<int> ans;
bool isUsed[MAXN];
int N;

void getPrimeTable() {  //筛选法求质数
    fill(isPrimeNum, isPrimeNum + MAXN, true);  //先假设都是素数
    isPrimeNum[0] = isPrimeNum[1] = false;
    for (int i = 2; i < MAXN; i++) {    //从2开始，因为2是最小的质素
        if (isPrimeNum[i]) {
            //把i的倍数全部设置成非质数
            //比如i=2，则把4、6、9...设置成非质数
            //若i=3，则把6、9、12、15...设置成非质数
            for (int j = 2 * i; j < MAXN; j += i) { //注意该for循环的写法，容易出错
                isPrimeNum[j] = false;
            }
        }
    }
}

void DFS(int index) {
    if (index >= N) {
        int temp = ans[0] + ans[index - 1]; //判断第一个数和最后一个数相加后是否是质数
        if (isPrimeNum[temp] == false) return;
        for (int x : ans) {
            printf("%d ", x);
        }
        printf("\n");
        return;
    }
    for (int i = 2; i <= N; i++) {
        if (isUsed[i]) continue;
        int temp = ans[index - 1] + i;
        if (isPrimeNum[temp] == false) {
            continue;   //剪枝
        }
        ans.push_back(i);
        isUsed[i] = true;
        DFS(index + 1);
        ans.pop_back();
        isUsed[i] = false;
    }
}

int main() {
    getPrimeTable();
    N = 4;
    ans.push_back(1);   //素数环第一个数固定是1
    DFS(1); //从第二个数开始搜索

    return 0;
}

---