当前位置： 首页 > article >正文

递归1——递归入门

article 2024/12/5 3:47:45

目录

1.递归

2.递归的基本题目

2.1.题目一——P5739 【深基7.例7】计算阶乘 - 洛谷 | 计算机科学教育新生态

2.2.题目二——B2064 斐波那契数列 - 洛谷 | 计算机科学教育新生态 

2.3.题目三——B2142 求 1+2+3+...+N 的值 - 洛谷 | 计算机科学教育新生态

2.4.题目四——B2144 阿克曼（Ackermann）函数 - 洛谷 | 计算机科学教育新生态 

2.5.题目五——B2145 digit 函数 - 洛谷 | 计算机科学教育新生态 

2.6.题目六——B2147 求 f(x,n) - 洛谷 | 计算机科学教育新生态 

2.7.题目七——B2148 再求 f(x,n) - 洛谷 | 计算机科学教育新生态 

2.8.题目八——B2143 进制转换 - 洛谷 | 计算机科学教育新生态 

3.二叉树里面的递归

3.1.题目一——100. 相同的树 - 力扣（LeetCode）

3.2.题目二——101. 对称二叉树 - 力扣（LeetCode） 

3.3.题目三 ——572. 另一棵树的子树 - 力扣（LeetCode）

3.4.题目四——144. 二叉树的前序遍历 - 力扣（LeetCode）

3.5.题目五——94. 二叉树的中序遍历 - 力扣（LeetCode）

3.6.题目六——145. 二叉树的后序遍历 - 力扣（LeetCode） 

 

从这章，我们先讲递归，然后讲搜索，然后再讲回溯算法。

1.递归

  • 什么是递归

我只讲3个东西来讲递归

  1. 二叉树的遍历
  2. 快排：先选一个基准元素，将数组分成3部分，然后让左边部分进行排序，再让右边部分排序
  3. 归并：取数组中点，让数组分成两部分，然后先让左边部分先排序，再让右边部分排序，然后合并两个数组
  •  为什么会用到递归？

本质就是这个问题可以拆分为多个相同的子问题，子问题又可以拆分成相同的子问题。

这个就像是数学的F(x,y)通用的。

  • 如何理解递归？

1.画递归展开的细节图

2.二叉树的题目

3.宏观看待递归

  • 不要在意递归的细节展开图
  • 把递归的函数当成一个黑盒
  • 相信这个黑盒一定能完成任务
  • 此外，我们一定要设置递归结束的地方

我们只关心当前的这个任务能不能顺利完成，如果当前可以完全，那么递归一定也可以（注意要加一个结束条件），就像下面这样子

 

  • 如何写好一个递归
  1. 我们先找到一个相同的子问题  ->   这个决定了函数头的设计
  2. 我们只关心某一个子问题是怎么解决的 ->这个决定函数体的书写
  3. 注意一下递归函数的出口——>就是什么时候不能递归的时候，就让函数返回

2.递归的基本题目

2.1.题目一——P5739 【深基7.例7】计算阶乘 - 洛谷 | 计算机科学教育新生态

这题其实非常简单

#include<iostream>
using namespace std;

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

int main()
{
    int a;
    cin>>a;
    cout<<fact(a)<<endl;
}

 

2.2.题目二——B2064 斐波那契数列 - 洛谷 | 计算机科学教育新生态 

这题还是很简单的

#include<iostream>
using namespace std;

int res(int n)
{
    if(n==1||n==2)
        return 1;
    else
        return res(n-1)+res(n-2);
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int m;
        cin>>m;
        cout<<res(m)<<endl;
    }
}

 

 

2.3.题目三——B2142 求 1+2+3+...+N 的值 - 洛谷 | 计算机科学教育新生态

很简单的题目，不必多说 

#include<iostream>
using namespace std;

int res(int n)
{
    if(n==1)
        return 1;
    else
        return res(n-1)+n;
}

int main()
{
    int m;
    cin>>m;
    cout<<res(m)<<endl;
}

 

 

2.4.题目四——B2144 阿克曼（Ackermann）函数 - 洛谷 | 计算机科学教育新生态 

这个理解题目很重要啊

#include<iostream>
using namespace std;

int akm(int m,int n)
{
    if(m==0)
        return n+1;
    else if(m>0&&n==0)
        return akm(m-1,1);
    else
        return akm(m-1,akm(m,n-1));
}

int main()
{
    int m,n;
    cin>>m>>n;
    cout<<akm(m,n)<<endl;
}

 

 

2.5.题目五——B2145 digit 函数 - 洛谷 | 计算机科学教育新生态 

这里就上了一点难度了啊，怎么做呢？ 

我们知道

  1. n/10就能减去n最右边那个数字
  2. n%10就能获得最右边那个数字

而我们题目要的是右边第k个数字，说明我们最后的结果一定是n%10出来的。

所以终止条件就是当k==1的时候，直接返回n%10即可。

这样子我们就很容易写出下面这个代码

#include<iostream>
using namespace std;

int digit(int n,int k)
{
    if(k==1)
        return n%10;
    else
        return digit(n/10,k-1);
}

int main()
{
    int n,k;
    cin>>n>>k;
    cout<<digit(n,k)<<endl;
}

2.6.题目六——B2147 求 f(x,n) - 洛谷 | 计算机科学教育新生态 

这个还是非常简单的

#include<iostream>
#include<cmath>
using namespace std;

float f(float x,int n)
{
    if(n==1)
        return sqrt(1+x);
    else
        return sqrt(n+f(x,n-1));
}

int main()
{
    float x;
    int n;
    cin>>x>>n;
    printf("%.2f\n", f(x,n));
}

  

2.7.题目七——B2148 再求 f(x,n) - 洛谷 | 计算机科学教育新生态 

这个明眼人就看出来了！！

#include<bits/stdc++.h>
using namespace std;

float f(float x,int n)
{
    if(n==1)
        return x/(1+x);
    else
        return x/(n+f(x,n-1));
}

int main()
{
    float x;
    int n;
    cin>>x>>n;
    printf("%.2f\n",f(x,n));
}

 

2.8.题目八——B2143 进制转换 - 洛谷 | 计算机科学教育新生态 

 

 这题上强度了啊！！！

首先我们得知道，这个题目的最大进制是16进制，所以我们必须得能表示16进制，那我们怎么快速的表示一个16进制的数字呢？

我们可以使用一个string，然后下标和这个数字一一对应。

其中2——16进制的所有表达方式都能在上面这个s里面找到。

接着，我们仔细看下面这个步骤

我们发现是不是好像有规律啊？

最后递归得到的就是最高位的数字，我们完全可以让它先出来。

看完之后，有没有通透一点，就是我们完全可以写出下面这个代码

 #include <iostream>
 using namespace std;
 string s = "0123456789ABCDEF";
 void x_to_m(int x, int m)
 {
    if (x >= m)
        x_to_m(x / m, m);
    cout << s[x % m];
 }
 int main()
 {
    int x = 0;
    int m = 0;
    cin >> x >> m;
    x_to_m(x, m);
    return 0;
 }

 

 

3.二叉树里面的递归

理解递归，上面的那些题目可不够，必须来看一下二叉树的递归。

3.1.题目一——100. 相同的树 - 力扣（LeetCode）

 

判断两棵二叉树是否相同，也可以将其分解为子问题：

  1. 比较两棵树的根是否相同。
  2. 比较两根的左子树是否相同。
  3. 比较两根的右子树是否相同。

代码：

class Solution {
public:
    // 判断两棵二叉树是否相同
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) // 两棵树均为空，则相同
            return true;
        if (p == NULL || q == NULL) // 两棵树中只有一棵树为空，则不相同
            return false;
        if (p->val != q->val) // 两棵树根的值不同，则不相同
            return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right,q->right); // 两棵树的左子树相同并且右子树相同，则这两棵树相同
    }
};

 

3.2.题目二——101. 对称二叉树 - 力扣（LeetCode） 

 

 

 

 

 对称二叉树，这里所说的对称是指镜像对称：

要判断某二叉树是否是对称二叉树，则判断其根结点的左子树和右子树是否是镜像对称即可。

因为是镜像对称，所以左子树的遍历方式和右子树的遍历方式是不同的，准确来说，左子树和右子树的遍历是反方向进行的。

如下图：

图中红蓝轨迹同时进行，同时结束。

  1. 若在遍历过程中发现镜像对称的某两个结点值不同，则无需继续遍历，此时已经可以判断该树不是对称二叉树
  2. 只有当红蓝轨迹成功遍历完毕后，才能断定该树是对称二叉树。

我们很快就能写出代码

class Solution {
public:
    // 判断镜像位置是否相等
    bool travel(TreeNode* left, TreeNode* right) {
        if (left == NULL && right == NULL) // 红蓝轨迹同时遍历到NULL，函数返回
            return true;
        if (left == NULL ||
            right ==
                NULL) // 红蓝指针中，一个为NULL，另一个不为NULL，即镜像不相等
            return false;
        if (left->val != right->val) // 红蓝指针指向的结点值不同，即镜像不相等
            return false;
        // 子问题：左子树遍历顺序：先左后右，右子树遍历顺序：先右后左。若两次遍历均成功，则是对称二叉树
        return travel(left->left, right->right) &&
               travel(left->right, right->left);
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) // 空树是对称二叉树
            return true;
        return travel(root->left, root->right); // 判断镜像位置是否相等
    }
};

3.3.题目三 ——572. 另一棵树的子树 - 力扣（LeetCode）

 

 

 

思路：
依次判断以 root 中某一个结点为根的子树是否与subRoot相同。 

class Solution {
public:
    // 比较以root和subRoot为根结点的两棵树是否相等
    bool Compare(TreeNode* root, TreeNode* subRoot) {
        if (root == NULL && subRoot == NULL) // 均为空树，相等
            return true;
        if (root == NULL || subRoot == NULL) // 一个为空另一个不为空，不相等
            return false;
        if (root->val != subRoot->val) // 结点的值不同，不相等
            return false;
        // 比较两棵树的子结点
        return Compare(root->left, subRoot->left) &&
               Compare(root->right, subRoot->right);
    }
    // 另一个树的子树
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        if (root == NULL) // 空树，不可能是与subRoot相同（subRoot非空）
            return false;
        if (Compare(root,
                    subRoot)) // 以root和subRoot为根，开始比较两棵树是否相同
            return true;
        // 判断root的左孩子和右孩子中是否有某一棵子树与subRoot相同
        return isSubtree(root->left, subRoot) ||
               isSubtree(root->right, subRoot);
    }
};

 

 

3.4.题目四——144. 二叉树的前序遍历 - 力扣（LeetCode）

 

二叉树的前序遍历不知道是什么？自己去这里看看：链式二叉树的基本操作1-CSDN博客

class Solution {
public:
    // 前序遍历的递归函数
    // 参数ret用于存储遍历的结果，root是当前遍历到的节点
    void preorder(vector<int>& ret, TreeNode* root)
    {
        // 如果当前节点为空，直接返回，不执行任何操作
        if(root == NULL)
            return;    
        // 将当前节点的值添加到结果集ret中
        ret.push_back(root->val);
        // 递归遍历左子树
        preorder(ret, root->left);
        // 递归遍历右子树
        preorder(ret, root->right);
    }
    
    vector<int> preorderTraversal(TreeNode* root) {
        // 创建一个向量ret，用于存储遍历的结果
        vector<int> ret; 
        // 调用递归函数preorder进行前序遍历，并将结果存储在ret中
        preorder(ret, root);
        // 返回存储遍历结果的向量
        return ret;
    }
};

3.5.题目五——94. 二叉树的中序遍历 - 力扣（LeetCode）

 

 

这题非常简单啊，我不想过多赘述啊！

class Solution {
public:
    // 中序遍历的递归函数
    // 参数ret用于存储遍历的结果，root是当前遍历到的节点
    void inorder(vector<int>& ret, TreeNode* root)
    {
        // 如果当前节点为空，直接返回，不执行任何操作
        if(root == NULL)
            return;    
        // 递归遍历左子树
        inorder(ret, root->left);
        // 将当前节点的值添加到结果集ret中
        // 此时，左子树的所有节点值都已经被添加到ret中了
        ret.push_back(root->val);
        // 递归遍历右子树
        // 此时，当前节点的值也已经被添加到ret中了
        inorder(ret, root->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        // 创建一个向量ret，用于存储遍历的结果
        vector<int> ret; 
        // 调用递归函数inorder进行中序遍历，并将结果存储在ret中
        inorder(ret, root);
        // 返回存储遍历结果的向量
        return ret;
    }
};

3.6.题目六——145. 二叉树的后序遍历 - 力扣（LeetCode） 

class Solution {
public:
    // 后序遍历的递归函数
    // 参数ret用于存储遍历的结果，root是当前遍历到的节点
    void postorder(vector<int>& ret, TreeNode* root)
    {
        // 如果当前节点为空，直接返回，不执行任何操作
        if(root == NULL)
            return;        
        // 递归遍历左子树
        postorder(ret, root->left);    
        // 递归遍历右子树
        postorder(ret, root->right);
        // 将当前节点的值添加到结果集ret中
        // 此时，左子树和右子树的所有节点值都已经被添加到ret中了
        ret.push_back(root->val);
    }
    vector<int> postorderTraversal(TreeNode* root) {
        // 创建一个向量ret，用于存储遍历的结果
        vector<int> ret; 
        // 调用递归函数postorder进行后序遍历，并将结果存储在ret中
        postorder(ret, root);
        // 返回存储遍历结果的向量
        return ret;
    }
};


http://www.kler.cn/a/419718.html

相关文章：

  • LeetCode 64. 最小路径和(HOT100)
  • Flutter 之 InheritedWidget
  • Linux - 远程连接服务器
  • LearnOpenGL学习（光照 -- 颜色，基础光照，材质，光照贴图）
  • 实时数据开发 | Flink的数据分区策略--物理分区操作
  • 我们来学mysql -- 事务并发之脏写(原理篇)
  • 计算机网络复习2——物理层
  • C++多线程——原子操作（atomic）
  • Ardusub源码剖析——control_manual.cpp
  • 【网络安全设备系列】1、防火墙
  • Electron-vue 框架升级 Babel7 并支持electron-preload webapck 4 打包过程记录
  • 二分法篇——于上下边界的扭转压缩间，窥见正解辉映之光（2）
  • 【深度学习】利用Java DL4J 优化金融投资组合
  • Equirectangular to Perspective（E2P）算法详解（附代码）
  • 从最浅层剖析C语言————第六节（深入了解数组传参、嵌套调用以及链式访问）
  • UI设计从入门到进阶，全能实战课
  • 源码分析之Openlayers的核心EventTarget类的实现
  • Python 列表操作详解
  • 深入解析数据结构：红黑树、哈希Map、B树与B+树的底层逻辑
  • ctfhub web技能树篇
  • 基于 PostgreSQL 和 PostGIS 数据服务器模式的设计方案
  • 高斯消元——acwing
  • C++stack、queue
  • npm安装依赖后报错
  • 【计算机网络】实验6：IPV4地址的构造超网及IP数据报
  • Go运行Grule引擎实现计费规则管理