学习
实践
活动
专区
工具
TVP
写文章

算法——递归

背景 最近遇到一个类似爬楼梯的算法题。索性对递归的处理总结一下。 爬楼梯题目 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 递归,去的过程称为“递”,回来的过程称为“归”。一般所有的递归问题都可以用递归公式来解决。写出递归公式,问题就解决了一多半。 如果递归深度多大,导致栈不够用,就会导致 StackOverflowError。如解法1,当n足够大,就会导致这个问题。 如何尽量避免? 限制递归深度;比方说当递归深度到达100的时候,就停止递归。 那么怎么计算递归算法的时间复杂度呢?其实在所有的递归问题中,因为是大问题拆分小问题的思路,所以整个计算过程算下来就好像是一棵树。 ? 这就是利用递归树求解递归的时间复杂度。 以上。。。 王争 《数据结构和算法之美》

17410
  • 广告
    关闭

    热门业务场景教学

    个人网站、项目部署、开发环境、游戏服务器、图床、渲染训练等免费搭建教程,多款云服务器20元起。

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    递归算法

    前言 递归算法(英语:recursion algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。 计算理论可以证明递归的作用可以完全取代循环,因此在很多函数编程语言(如Scheme)中习惯用递归来实现循环。 应用场景 数据的定义是按递归定义的。如Fibonacci函数。 问题解法按递归算法实现。如Hanoi问题。 数据的结构形式是按递归定义的。如二叉树、广义表等。 第三:递归函数中,位于递归调用前的语句和各级被调函数具有相同的执行顺序。 第四:递归函数中,位于递归调用后的语句的执行顺序和各个被调函数的顺序相反。 第五:虽然每一级递归都有自己的变量,但是函数代码不会复制。 第六:递归函数中必须包含终止递归的语句。

    49320

    算法--递归

    本文链接:https://ligang.blog.csdn.net/article/details/83757651 递归 函数直接或间接调用函数本身。 递归是一种计算过程,如果其中每一步都要用到前一步或前几步的结果,称为递归的。用递归过程定义的函数,称为递归函数。它解决问题的各个小部分,直到解决最初的大问题。 在有限次(必须有出口)可预见性结果中,找到结果与上一次结果之间的关系; 关键在于梳理清楚本次结果和上一次结果的关系有哪些方面或是因素; 在算法的分析中,当一个算法中包含递归调用时,其时间复杂度的分析会转化成为一个递归方程的求解 经典递归案例: 示例: 斐波那契数列:1、1、2、3、5、8、13、21、34 F(0) = 0; F(1) = 1; F(n) = F(n-1) + F(n-2) function fibonacci 1 : fibonacci(n - 1) + fibonacci(n - 2) } })() 示例: 最大公约数,采用辗转相除法(欧几里得算法) 定理:两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数

    23021

    全排列递归算法_全排列递归算法

    一 全排列算法 首先:什么是全排列=》百度一下 从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。 =1) 算法递归算法=》网络上偷了一个图 全排列:顺便复习一个数学公式 排列的定义:从n个不同元素中,任取m(m≤n,m与n均为自然数,下同)个元素按照一定的顺序排成一列,叫做从n个不同元素中取出m namespace std; //交换 void swap(int &a , int &b) { int temp; temp = a; a = b; b = temp; } //全排列递归算法 每次固定几位数,最后只剩一位数,输出,在从后面递归返回上一层,交换在输出 for(int i=k;i<=m;i++) { list[k]); } 代码解析”” int i=k K表示固定了几位数,当前数组交换的临界的位置 1,2,3,4 当K=0的时候 {1,2,3,4} =》1是固定的 K+1递归

    16310

    递归算法

    对于很多编程初学者来说,递归算法是学习语言的最大障碍之一。很多人也是半懂不懂,结果学到很深的境地也会因为自己基础不好,导致发展太慢。 可能也有一大部分人知道递归,也能看的懂递归,但在实际做题过程中,却不知道怎么使用。今天,我们就来说一说递归算法的使用。 什么是递归 递归,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。 也就是说,递归算法是一种直接或者间接调用自身函数或者方法的算法。 通俗来说,递归算法的实质是把问题分解成规模缩小的同类问题的子问题,然后递归调用方法来表示问题的解。 编写正确的递归算法,一定要有 ”归“ 的步骤,也就是说递归算法,在分解问题到不能再分解的步骤时,要让递归有退出的条件,否则就会陷入死循环,最终导致内存不足引发栈溢出异常。 下面,我们通过两个例子来学习一下,递归的使用: 例一:递归求阶乘 图片 例二:递归求斐波那契数列 图片 从上面的步骤我们可以清晰的看到递归算法的第一步是分治,把复杂的大的问题,给拆分成一个一个小问题,直到不能再拆解

    9020

    算法渣-递归算法

    前言 之前的排序算法 《快速排序》 与 《归并排序》 都使用了递归手法,如果不能理解递归,那分治思想类算法实现就难以理解 递归 To iterate is human,to recurse divine Peter Deutsch 迭代的是人,递归的是神 递归思想 递归的基本思想是把规模大的问题转化为规模小的相似的子问题来解决。 另外这个解决问题的函数必须有明显的结束条件,这样就不会产生无限递归的情况了。 递归中的“递”就是入栈,递进;“归”就是出栈,回归 规模大转化为规模小是核心思想,但递归并非是只做这步转化,而是把规模大的问题分解为规模小的子问题和可以在子问题解决的基础上剩余的可以自行解决的部分。 VS迭代 递归算法与迭代算法的设计思路区别在于:函数或算法是否具备收敛性,当且仅当一个算法存在预期的收敛效果时,采用递归算法才是可行的,否则,就不能使用递归算法 参考资料 怎么更好地终极理解递归算法

    22230

    算法-递归算法-阶乘

    /** * 递归算法 * 递归算法是很常用的算法思想。使用递归算法,往往可以简化代码编写,提高程序的可读性。但是,不合适的递归往往导致程序的执行效率变低。 * 递归算法即在程序中不断反复调用自身来达到求解问题的方法。此处的重点是调用自身,这就要求待求解的问题能够分解为相同问题的一个子问题。这样,通过多次递归调用,便可以完成求解。 * 方法的递归调用分两种情况:直接递归和间接递归 * 直接递归,即在方法中调用方法本身。 * 间接递归,即间接地调用一个方法,如func_a调用func_b,func_b又调用func_a。 * 递归优点: * 程序代码更简洁清晰,可读性更好。有的算法递归表示要比用循环表示简洁精练,而且某些问题,特别是与人工智能有关的问题,更适宜用递归方法,如八皇后问题、汉诺塔问题等。 有的算法,用递归能实现,而用循环却不一定能实现。 * 递归缺点: * 大部分递归例程没有明显地减少代码规模和节省内存空间。递归形式比非递归形式运行速度要慢一些。

    36540

    递归下降算法_递归算法经典实例

    递归下降算法 算法模型: Term = Term + Expr Expr=Expr+Factor Factor =单个元素。最小单位。 实现原理: 一个程式进入算法及被看作是一个项,分解成项加表达式的形式,表达式被分解成 表达式加因子的形式,因子是这个算法中的最小单位。 上一级调用比自己小一级的自己。 我用递归下降算法写了个简单的计算器,递归算法为我的运算符号+ - * / 等基础运算符号形成优先级。在使用的过程中发现了递归下降算法很容易产生的一个问题,左递归问题。 什么叫左递归? 举个例子:1-2+1 正确答案应该是0,如果出现左递归答案将会是-2。 解决方案: 将运算符号抽象出来单独成立一层,将数值节点统统存入Vector,这样的话,在实际生成到内存中需要判断优先级的只有+ - * / 四个了,因为递归下降算法,所以只要让 * /在+ -的下一级子类中生成

    12710

    什么是php递归算法_PHP递归算法(一)

    在前面的文章中,我们为大家介绍了PHP算法系列之《PHP随机取一算法》和《PHP冒泡排序算法》,需要的朋友可以了解学习。本篇文章我们将继续为大家带来常见的PHP算法,即PHP递归算法。 在PHP开发过程中,递归算法通常用于无限极分类。那么所谓递归就是一种函数调用自身的机制。 并且递归算法的实现方法是有多种的,如通过“静态变量”、“全局变量”、“引用传参”的方式。 下面我们就结合具体的代码示例,给大家介绍其中一种方法即利用静态变量的方法! 代码如下:<? echo $i . ”; $i++; if($i<10){ call(); } } call(); 输出:0 1 2 3 4 5 6 7 8 9 这种方法我们主要利用static定义静态变量来实现递归排序 本篇文章就是关于利用静态变量实现PHP递归算法的介绍,在后续的文章中,我们会继续为大家介绍PHP递归算法的相关实现方法。

    9710

    算法(一) 递归

    递归的核心:对于一个节点来说,它只需要知道它之后的所有节点操作之后的结果就可以了。 个人总结三要素: 确定递归函数的参数和返回值。 确定终止条件。 确定单个递归的内容。 例题 1,反转链表(递归,双指针 ) 来自 LeetCode206 补充: * public class ListNode { * int val; * ListNode 理解(不保证正确) 1,递归想对于迭代,代码会更加清晰一些。 2,递归分两种 一种是return 递归式,求的是最后一个递归式的结果,作为整个函数的结果。 一种是过程中递归式,更多是类似于动态规划,每一层递归都是给前一阵作为实现的基石。 递归思想中,不应该考虑每一步递归的过程,这样大概率出错。应该考虑当前递归我需要得到的结果就可以了。 3,二叉树遍历 在算法(八)那篇文章里。 很重要。(不过递归算法太简单不是很重要)

    10360

    java中的递归算法_java递归算法详解

    Java中的递归算法虽然简单,但想要精通也是有着一定的难度的,本篇文章我们就来详细了解下递归算法。 什么是递归? 一般的说, 递归算法是一种直接或间接地调用自身的算法。 在程序中,递归算法能够使算法的描述简洁而且易于理解。 递归分几类? 递归通常分为两类,直接递归和间接递归: 1、直接递归称为方法自身调用自己。 2、间接递归可以A方法调用B方法,B方法调用C方法,C方法调用A方法。 递归怎么实现实现? 例://递归实现九九乘法表 public class diguidemo { public static void main(String[] args) { digui(9); } private – 1); for (int j = 1; j <= 1; j++) { System.out.print(j + “*” + i + “=” + j * i + ” “); } } } } //递归求和

    15220

    递归算法(下)

    上文讲了递归算法比较简单的用法,相信对递归算法有一定的概念了。这篇文章再来试试两个相对复杂一点点的案例,最后在总结一下使用递归的一般方法已经需要注意的地方。 汉诺塔 汉诺塔是一种移动圆盘的游戏,同时也是一个简单易懂的递归算法应用示例。(案例及图片来源于《我的第一本算法书》) 游戏规则 ? 移动一个盘子: 直接移动 盘子1 从A-->C 移动两个盘子: ? 理解 n =3时的详细流程图理解,红色部分表示会递归调用函数,黄色部分是结果。 递归的三要素 1. 明确递归终止条件。 2. 给出递归终止时的处理办法,一般地,在这种情境下,问题的解决方案是直观的、容易的。 3.. 提取重复的逻辑,缩小问题规模。 递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题,这些子问题可以用相同的解题思路来解决。

    32911

    递归算法使用

    1.什么是递归算法 通常递归算法可以将一个问题的重复调用进行分解,将其分解成一个多次调用,最终完成筛选或者需要的数据。 这样我们就可以进行我们的递归操作了。 如果需要进行递归,此时我们首先需要进行设计事先在文件目录中涉及一个顶尖目录,它是以0开头的。然后后面的都是可以依次为基础的。 3.遇到的问题和解决 想写好递归,首先想好需要写的关系,这样递归就可以很好的写出来了。在这过程中,我也遇到过,当时文件上传的时候,我在本地测试上传的时候,没有什么问题。 4.总结 什么时候该使用递归,遇到的问题是重复性操作,同时有终止的条件,可以进行递推,此时就可以考虑。同时这个问题可以进行分解。递归的使用还是很广泛的,比如机器学习中,经常基于一个公式进行递推。 比如常用的菜单树,都是可以使用递归的。

    22930

    算法递归

    递归是一种很常见的算法,许多循环算法可以转变成递归。 ; // 2 } 也就是递归一般会有一个判断,这是递归算法的出口(1 处);还有一个返回这个函数的执行结果(2 处);这两点是实现递归的关键。 要理解递归需要先了解递归的运行机制。许多递归算法可以由循环来实现,但是用递归有时会更简洁一些。 案例 递归算法中应用十分广泛,相较于循环迭代,递归显得更加优雅直观,代码易读性好一些。但是使用递归并不一定比迭代运行速度快,递归需要先递推后回溯,而迭代没有那么多的过程。 在一般的递归函数中,是首先执行递归调用,然后获取递归调用的返回值并计算结果;而尾递归首先执行计算,然后执行递归调用,将当前步骤的结果传递给下一个递归步骤,尾递归也是为了优化递归算法

    29010

    算法递归

    递归是一种应用非常广泛的算法,在很多的数据结构和算法的编码中都会用到,理解递归是非常重要的。 ---- 递归就这样完成了,上面这个例子是只有一个递归调用的分支,还是比较好理解的,如果有多个递归分支的话,单纯靠人脑是很难理解清楚的,计算机比较适合做重复的工作,我们如果一环一环往递归里走的话,很快就迷糊了 ,唯一的方法就是自己屏蔽掉其中细节,只把握好第一个递归公式的构造和终止条件的判断,就能更好的理解清楚递归了。 ,如果递归太深,压入栈中的数据是非常多的,就会有堆栈溢出的风险;解决办法就是在递归函数中加入一个判断条件,来判断递归的深度,如果达到了某一个值,就直接返回报错。 为了避免这些情况,也可以将递归代码改为迭代循环的非递归方式,就是使用循环的方式来进行处理。 参考文档 极客时间-数据结构与算法之美

    21810

    关注

    腾讯云开发者公众号
    10元无门槛代金券
    洞察腾讯核心技术
    剖析业界实践案例
    腾讯云开发者公众号二维码

    相关产品

    • DNS 解析 DNSPod

      DNS 解析 DNSPod

      域名解析(DNS解析)是域名转换为机器可读的IP地址的过程。腾讯 DNS 解析 DNSPod 向全网域名提供免费的智能域名解析服务,拥有海量处理能力、灵活扩展性和安全能力。

    相关资讯

    热门标签

    活动推荐

    扫码关注腾讯云开发者

    领取腾讯云代金券