递归算法轻松学：专为新手小白打造的入门指南，新手必做树递归遍历，斐波那契数，辗转相除计算最大公约数，前后中缀表达式，DES回溯遍历，全排列问题-天翼云

`递归入门`

`编写一个递归函数`

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

`计算阶乘(factorial)`

解析：

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

递归算法轻松学：专为新手小白打造的入门指南，新手必做树递归遍历，斐波那契数，辗转相除计算最大公约数，前后中缀表达式，DES回溯遍历，全排列问题

#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）
分而治之（每次让问题的规模减半）（归并排序的思想）

`例题：走楼梯`

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

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

解析：

只有一个台阶，只有一种走法：一次走一步
有两个台阶，有两种走法：两次一步，一次两步
假设我们站在第 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，则继续对子数组进行分割，直到每个子数组只包含一个元素为止。
排序：
- 对于每个只包含一个元素的子数组，可以认为它们已经是有序的。
- 然后，从底层开始，逐步合并相邻的两个有序子数组，得到更大的有序数组。
合并：
- 合并时，需要比较两个子数组的元素，依次将较小的元素放入新的合并后的数组中。
- 重复这个过程，直到所有的子数组都被合并成一个完整的有序数组。

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);  //最后访问根节点
}

`层次遍历`

代码解析：

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

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

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

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）

输出格式：

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

样例输入：

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

(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）

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

使用全局变量

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--;
}

使用函数传参（值传递）

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);
}

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

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--;
}

求节点路径

使用全局数组

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();
}

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

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;
}

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

递归算法轻松学：专为新手小白打造的入门指南，新手必做树递归遍历，斐波那契数，辗转相除计算最大公约数，前后中缀表达式，DES回溯遍历，全排列问题

递归算法轻松学：专为新手小白打造的入门指南，新手必做树递归遍历，斐波那契数，辗转相除计算最大公约数，前后中缀表达式，DES回溯遍历，全排列问题

递归入门

编写一个递归函数

计算阶乘(factorial)

计算斐波那契数列

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

分治算法

例题：走楼梯

归并排序

二叉树、树

二叉树的遍历

前序遍历

中序遍历

后序遍历

层次遍历

求二叉树的高度

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

求某节点到根节点的路径

求某节点所在层数

求节点路径

普通树的遍历

DFS/回溯算法

全排列问题

素数环问题

相关文章

通过删除使数组中的所有元素都大于或等于k

用go语言，给定一个下标从1开始，包含不同整数的数组 nums，数组长度为 n。

用go语言，给定一个从 0 开始索引的整数数组 nums 和一个整数 k，请设计一个算法来使得数组中的所有元素都大于或等于 k，返回所需的最少操作次数。

文心一言 VS 讯飞星火 VS chatgpt （321）-- 算法导论22.3 13题

数组分割

Redis分区指南：如何实现高可用与扩展性

分布式一致性必备：一文读懂Raft算法

解决Paxos活性难题：分布式一致性的终极指南

文心一言 VS 讯飞星火 VS chatgpt （289）-- 算法导论21.3 2题

文心一言 VS 讯飞星火 VS chatgpt （287）-- 算法导论21.2 6题

作者介绍

最新文章

分布式一致性必备：一文读懂Raft算法

解决Paxos活性难题：分布式一致性的终极指南

用go语言，你有一个包含 n 个整数的数组 nums。 每个数组的代价是指该数组中的第一个元素的值。 你的目标是将这个数组划分为三个连续且互不重叠的子数组。

用go语言，给定三个正整数 n、x 和 y， 描述一个城市中由 n 个房屋和 n 条街道连接的情况。

布尔表达式 是计算结果不是 true 就是 false 的表达式 有效的表达式需遵循以下约定： ‘t‘，运算结果为 true ‘f‘

股票问题4。给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。

热门文章

Kubernetes 为系统守护进程预留计算资源

数据结构与算法-二叉树的名词概念与相关数据的计算

Python数据分析与展示：科学计算基础库numpy-1

计算机算法设计与分析（1-6章 复习笔记）

深度分析Redis分布式锁在电商超卖业务场景下的使用

2、apache-kylin-3.1.3-bin-hadoop3集群部署

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

计算机小白的成长历程——数组（2）

分布式事务在Java中的实现与优化

数据结构之时间复杂度和空间复杂度的相关计算

股票问题3。给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

科学计算numpy库——基础入门

用go语言，你有一个包含 n 个整数的数组 nums。 每个数组的代价是指该数组中的第一个元素的值。 你的目标是将这个数组划分为三个连续且互不重叠的子数组。

`递归入门`

`编写一个递归函数`

`计算阶乘(factorial)`

`计算斐波那契数列`

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

`分治算法`

`例题：走楼梯`

`归并排序`

`二叉树、树`

`二叉树的遍历`

`前序遍历`

`中序遍历`

`后序遍历`

`层次遍历`

`求二叉树的高度`

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

`求某节点到根节点的路径`

`求某节点所在层数`

`普通树的遍历`

`DFS/回溯算法`

`全排列问题`

`素数环问题`

用go语言，你有一个包含 n 个整数的数组 nums。每个数组的代价是指该数组中的第一个元素的值。你的目标是将这个数组划分为三个连续且互不重叠的子数组。

用go语言，给定三个正整数 n、x 和 y，描述一个城市中由 n 个房屋和 n 条街道连接的情况。

布尔表达式是计算结果不是 true 就是 false 的表达式有效的表达式需遵循以下约定： ‘t‘，运算结果为 true ‘f‘

计算机算法设计与分析（1-6章复习笔记）

股票问题3。给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

用go语言，你有一个包含 n 个整数的数组 nums。每个数组的代价是指该数组中的第一个元素的值。你的目标是将这个数组划分为三个连续且互不重叠的子数组。