【编程基础】人人都应该懂得递归小知识

2024-05-09 15:20

本文主要是介绍【编程基础】人人都应该懂得递归小知识,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 什么是递归
    • 递归和栈
    • 尾递归
    • 递归和分治
      • 归并排序
    • 递归和树

什么是递归

下面引用刘汝佳的《算法竞赛入门经典》中对递归的定义:

  • 递归:参见递归。
  • 递归:如果你还不理解递归是什么,请参见递归。

递归事实上就是函数直接或间接调用自身的一个过程。(或者其它本质上相似过程的也可以称为递归。)但和许多基本的概念一样,定义总是很简洁,但真正运用起来却并不容易。
在程序设计中为了保证递归能够结束,递归函数一定需要一个结束条件,称这个条件为基线条件,满足基线条件时停止递归调用。

递归和栈

程序的执行有严格的顺序,不考虑并行算法的话,一个程序在某一时刻只能处理一条语句(或者说是不可能有两个计算的过程同时执行)。递归函数自然也是按一定顺序执行的。
函数调用函数的过程形成一个栈结构,称为调用栈

需要清楚:

  1. main()函数一定位于栈底
  2. 每调用一个函数,就将这个函数压入栈中
  3. 计算机当前处理的语句位于栈顶的函数中
  4. 当一个函数完全执行结束时(完全执行结束意味着这个函数调用的函数也已经执行结束),将这个函数从栈顶弹出。
  5. 递归函数在达到基线条件之前,递归函数是不断进行栈的压入,到达基线条件之后递归函数不断进行栈的弹出,直到到达递归入口
  6. 当main()函数从栈中弹出时,整个程序运行结束

由于递归函数不断地进行调用,通常递归函数容易产生层数较多的调用栈。递归函数一定可以使用一般的栈结构来模拟出来。

尾递归

尾递归是指容易用简单循环语句转化为非递归算法的一种递归。有时尾递归更类似于一种递推方法,例如求阶乘函数的尾递归写法:

int fun(int x,int ans=1){ if(x<=1)    return ans;else return fun(x-1,ans*x);
}
相当于函数:int fun(int x){int ans=1;for(int i=x;i>1;i--)    ans=ans*i;return ans;
}
而阶乘函数的非尾递归写法:int fun(int x){if(x<=1)    return 1;else return fun(x-1)*x;
}

通过对比尾递归和非尾递归的两种写法,不难发现尾递归算法在满足基线条件时就已经得到了想要的结果,而非尾递归算法满足基线条件时不能直接得到最终结果,而是将返回的值传递给上一层的递归函数,让上一层函数继续处理。有些地方对尾递归的定义中写道尾递归是可以转化为循环语句的递归,而其它递归是可以用栈来模拟的递归,这样的说法是不正确的,因为只要是递归,就可以使用栈来模拟。只是有时会复杂一些。

递归和分治

分治算法即不断划分子问题,最后合并的算法。容易得到分治的两个重点在于:

  • 划分
  • 合并子问题

由于分治算法划分的子问题一般具有相同的结构,也就具有相似的解决方案。所以很显然递归的思想可以用来实现分治算法。值得一提的是,划分子问题是为了利用子问题的结果得到合并后的那个问题的结果。即递归的上一层需要用到该层的结果,因此分治算法不属于尾递归算法。或者说可以用尾递归算法解决的问题不需要分治。

归并排序

归并排序是分治算法的一个典型的例子。

归并排序的基本思想在于:

如果一个数组的前半部分和后半部分都是有序的,那么就可以使用二路归并的方法将前半部分与后半部分合并,时间复杂度 O ( n ) O(n) O(n)
由第一条可以想到把一个数组中所有元素排序,可以先将元素分成相等的两部分排序,再按上一条的方法合并。

归并排序的代码:

void merge_sort(vector<int> &V){if(V.size()<=1) return;vector<int> A;vector<int> B;for(int i=0;i<V.size()/2;i++)   A.push_back(V[i]);for(int i=V.size()/2;i<V.size();i++)    B.push_back(V[i]);merge_sort(A),merge_sort(B);//二路归并,此时A和B都已经排过序V.clear();int p1=0,p2=0;while(p1<A.size()||p2<B.size()){if(p1>=A.size())    V.push_back(B[p2]),p2++;else if(p2>=B.size())   V.push_back(A[p1]),p1++;else{if(A[p1]<B[p2]) V.push_back(A[p1]),p1++;else V.push_back(B[p2]),p2++;}}
}

可以看到归并排序的函数中有两条调用自身的语句。这时称这个函数可以形成最多两条分支。当元素个数为10时归并排序的分支结构可以形象的表示为下图:
在这里插入图片描述

像这样的表示递归过程的图像可以称为解答树。将递归过程中由于递归产生栈的最大的层数成为递归的层数,很显然上图表示的过程层数为5。可以证明归并排序的层数不会超过 l o g n + 2 logn+2 logn+2,而每一层处理都需要 O ( n ) O(n) O(n)的时间,所以归并排序的时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)
用递归的层数乘以每层需要的时间也是分析递归函数时间复杂度的常用手段

递归和树

树是无环图。把树的一条边去掉,得到的两个部分仍然是树结构。或者可以说树可以由两个树通过一条边相连构成。

于是我们也可以用下面的方法定义树:

  • 一个点是一棵树
  • 两个树通过一条边相连得到的仍然是一棵树

树的定义是递归的,所以树结构用递归来处理最为合适。
用递归用来处理树的最常见的例子就是树的搜索,也叫树的遍历。有时也称作DFS(深度优先搜索)或BFS(广度优先搜索)。

这篇关于【编程基础】人人都应该懂得递归小知识的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/973751

相关文章

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

sqlite3 相关知识

WAL 模式 VS 回滚模式 特性WAL 模式回滚模式(Rollback Journal)定义使用写前日志来记录变更。使用回滚日志来记录事务的所有修改。特点更高的并发性和性能;支持多读者和单写者。支持安全的事务回滚,但并发性较低。性能写入性能更好,尤其是读多写少的场景。写操作会造成较大的性能开销,尤其是在事务开始时。写入流程数据首先写入 WAL 文件,然后才从 WAL 刷新到主数据库。数据在开始

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码: 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口,https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈? cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运维场景中的应用,旨在帮助运维人员快速上手并熟练运用 Ansible。 1. Ansible的核心概念

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close