您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

一文精通递归算法

时间:2022-10-07 09:34:29  来源:  作者:掂掂三生有幸

 

一、什么是递归?

自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。

  • 一个问题可以分解为多个子问题;
  • 当前问题与其子问题除了数据规模不同外,求解思路完全一样;
  • 存在递归终止条件;

二、为什么要使用递归?

理论上,任何递归代码都可以使用非递归的方式进行实现,那么为什么还要使用递归呢?

递归求解本质上是使用系统提供的栈来实现的,由系统为我们自动递归求解;如果改成非递归的方式,那么我们其实就是在手动递归,本质上这两种方式没有任何区别。但是相同的逻辑,两份代码,递归实现明显更加地简洁,更加有利系统的维护。

三、如何使用递归?

我们以一个实际的例子来演示如何使用递归。

假设,有n个台阶,我们一步可以跨一个台阶,也可以一步跨两个台阶,那么这n个台阶总共有多少种跨法?

我们按照递归使用的三个条件来分析下:

  • 是否可以分解为子问题?
  • 是的,我们跨上第n阶台阶时,要么是一步一个跨上去的,要么就是一步两个跨上去的,所以问题就分解为“跨上n-1个台阶有多少种跨法”+“跨上n-2个台阶有多少种跨法”,递推公式可以表示为f(n)=f(n-1)+f(n-2);
  • 当前问题和子问题的求解思路是否一样?
  • 是的
  • 是否存在终止条件?
  • 是的,当n为1的时候,就一种跨法,当n为2的时候有两种跨法,当n为3或者4的时候,可以拆解为子问题,所以终止条件就是f(1)=1,f(2)=2;

分析完之后,我们就得到了带终止条件的递推公式,再转换为代码即可:

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

递归的求解过程确实很难一下子就理解清楚,这是由于我们人脑的机制造成的,谁都会感觉这样。

我们应该假设子问题f(n-1)和f(n-2)已经得到求解,然后在此基础上去求解当前的问题f(n),得到一个递推公式,如此只思考两层之间的关联关系会简单很多,千万不要试图去分解和理解每个递归层次的过程。

四、使用递归需要注意什么?

4.1 堆栈溢出

当递归调用深度过深的时候,就很容易出现栈溢出的问题,此时最好的方法就是根据业务场景逻辑和JVM的栈大小确定一个合理的最大递归深度,当超过该深度值的时候,程序抛出异常;

4.2 重复计算

子问题的子问题可能会出现重复的问题,比如f(6)=f(5)+f(4),其中,f(5)和f(4)都会有子问题f(3),那么f(3)应该是不需要重复计算的。

我们可以将求解过的问题结果保存到散列表中,当递归调用执行时,先检查该问题是否已经求解过了,如果是那么直接从散列表中获取结果返回即可,只有没有求解过的问题,才继续递归调用;

int countSteps(int n){
    if(n == 1) {
        return 1;
    }
    if(n == 2) {
        return 2;
    }
    
    // 先从散列表中检查是否已经对f(n)求解过了
    if(resultMap.get(n) != null){
        return resultMap.get(n);
    }
    int result = f(n-1) + f(n-2);
    // 将当前问题f(n)结果保存到散列表
    resultMap.put(n,result);
    return result;
}

4.3 时空复杂度

空间复杂度方面,因为递归深度决定着栈的使用程度,所以空间复杂度为O(n);

时间复杂度上面,虽然入栈和出栈都是O(1),但是如果递归深度较大的话,函数上下文切换等造成的时间开销也会比较可观;

4.4 递归环

有时候,可能由于脏数据的问题,会导致递归环的存在,比如在找原始推荐人的时候,A推荐了B,B推荐了C,C推荐了D,然后有一条脏数据,导致A的推荐人是D,那么在递归寻找原始推荐人的时候,就会陷入环中,可以设置一个最大递归深度来解决这个问题。



Tags:递归算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
一文精通递归算法
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  Search: 递归算法  点击:(270)  评论:(0)  加入收藏
java递归算法的实例最细讲解
递归三要素:1、明确递归终止条件;2、给出递归终止时的处理办法;3、提取重复的逻辑,缩小问题的规模。1、1+2+3+…+nimport java.util.Scanner; public class Recursion {...【详细内容】
2022-03-18  Search: 递归算法  点击:(268)  评论:(0)  加入收藏
谷歌面试问题50%需要用递归:理解递归算法的本质这篇够不够?
你对递归很纠结吗?虽然代码量少,理解起来太费劲?如果你这么想那就对了。因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。可是程序员面试不得不准...【详细内容】
2020-06-21  Search: 递归算法  点击:(404)  评论:(0)  加入收藏
解读递归算法原理和效率
对于很多人来说,都知道递归,也能看的懂递归,但在实际项目过程中,却不知道如何使用递归,这里给递归做个总结。递归的定义在数学与计算机科学中,递归(Recursion)是指在函数的定义中...【详细内容】
2019-10-14  Search: 递归算法  点击:(752)  评论:(0)  加入收藏
递归算法其实很高效,深入探索递归
递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对...【详细内容】
2019-09-17  Search: 递归算法  点击:(1117)  评论:(0)  加入收藏
深入理解递归算法,被误解的递归
递归是一个神奇的算法,它是编程书籍中讲解的最尴尬部分。这些书籍通常会展示一个递归的阶乘实现,然后警告你,虽然它能运行但是它非常的慢并且可能会堆栈溢出而崩溃。虽然大家对...【详细内容】
2019-09-16  Search: 递归算法  点击:(600)  评论:(0)  加入收藏
使用python构建递归算法,实现查找电脑中的所有文件
最近在实际工作中遇到一个需求,需要检测一个大文件夹下所有文件的更新状态,这个大文件夹下面包含了很多文件和文件夹,文件夹中又包含了很多文件和文件夹...... 类似下面这张图...【详细内容】
2019-08-16  Search: 递归算法  点击:(983)  评论:(0)  加入收藏
递归算法
递归(recursion):程序调用自身的编程技巧。递归满足2个条件:1)有反复执行的过程(调用自身)2)有跳出反复执行过程的条件(递归出口)我这边自己的理解就是反复调用自己本身以前有写过简单...【详细内容】
2019-05-16  Search: 递归算法  点击:(1296)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(15)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(51)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(45)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(77)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(96)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(64)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(108)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(165)  评论:(0)  加入收藏
站内最新
站内热门
站内头条