点击围观!腾讯 TAPD 助力金融行业研发提效、敏捷转型最佳实践! 了解详情
写点什么

每个高效程序员都应该知道的递归高级概念

  • 2020-08-14
  • 本文字数:3447 字

    阅读完需:约 11 分钟

每个高效程序员都应该知道的递归高级概念

本文最初发表在 Towards Data Science 博客上,由 InfoQ 中文站翻译并分享。


递归是最强大的编程方法之一。它在程序员工具箱中的有用工具清单上名列前茅,能够以令人震惊的少量代码解决极其复杂的问题。然而,递归通常是一个难以理解的概念,因为它需要从非标准的角度来看待命令是如何处理的。


本文将从简单的示例开始,逐步过渡到更具挑战性的示例,并附有大量图表:


  • 递归的思维方式

  • 递归关系

  • 记忆化

  • 分治法策略


递归是一种解决问题的方法,其中,函数在函数定义内调用自身。每个递归实现都需要有两个元素:


  • 一个或多个 Base Case(边界条件、基准条件),它们是终止条件(Terminating Case),在这些条件中,不需要用更多的递归来进一步寻找答案。

  • 一组规则(递归关系),通过启动另一轮递归,将其他条件减少到一个 Base Case。


例如,让我们考虑反向打印字符串。输入 “hello” 的输出应为 “olleh”。完成这一任务的贴袋方法是使用 for 循环,并打印出从最后一个索引到第一个索引的每个字符。



递归方法将首先创建一个函数 reverseString ,它接受一个字符串作为参数。如果输入的长度不为 0(则将作为 Base Case 或终止条件),我们将打印最后一个字母,并在当前字符串上启动另一个 reverseString 示例,但不包括最后一个字符串(因为它刚刚被打印)。



请注意,因为该函数是在其内部调用的,所以它自己创建了一个 for 循环。此外,在调用该函数的另一个实例之前必须存在 if 语句。否则,将抛出 RecursionErrorRuntimeError 错误,因为脚本认为这个无线循环没有结束。这类似于 while True 无限循环。


让我们看看这个递归函数在 “hello” 上是如何起作用的:



在比较复杂的问题上进行递归是一件很困难的事情,因为确定它的两个组成部分——递归关系,即一个问题的结果与其子问题的结果之间的关系;在 Base Case 下,则是无需任何递归调用就可以直接计算的情况。有时,Base Case 又称为 Bottom Case,因为在这种情况下,问题已经缩小到最小的规模。


例如,杨辉三角形(Pascal’s triangle)中,其中每个数字都是它上面两个数字的和,三角形边上都有数字。如何使用递归来查找点 (i,j) 上任何值的值?递归关系的 Base/Terminatin Case 是什么?



递归关系可以用下面的公式来表示:



这在观察这个三角形的图时,是显而易见的。这个公式更好的地方在于,如果我们继续用这个公式把任意位置 (i,j) 分解为另外两个位置的和,那么就不可避免会导致 Base Case——1。杨辉三角形从 1 开始,从 1 的和开始,一个完整的复杂图案就出现了。


我们如何实现呢?


首先,让我们找到一组规则,确定何时满足 Base Case:单元格的值等于 1。注意,1 在两种情况下出现:要么位于第一列 (j=0) ,要么位于对角线 (i=j) 上。



现在实现起来很简单,如果满足 Base Case,则返回基值 (1)。否则,我们将继续减少问题,直到达到一个 Base Case,我们已经确定任何输入都将不可避免地被分解成 Base Case。



到现在为止,你应该已经领悟到递归之美了。在本文中,我们实际上用五行代码创建了一个自构造树(self-building tree)(如果你想缩短它,甚至也可以是三行代码)。当我们两次调用 pascal 函数时,启动了两个搜索分支,每个分支又启动另外两个,假设它们没有达到 Base Case。


递归是如何有效地工作的,这可能有点不可思议、令人困惑。让我们来通过一个例子来了解递归算法是如何运行的。


根据我们的递归关系,(4,2) 被分解成它上面的两个数 (3,1) 和 (3,2)。请注意,算法实际上并不知道这些单元格的值是 3,它所做的只是记录它们的位置。我们并不知道也不关心任何值,除非它能满足我们的 Base Case。根据我们的 Base Case (1),我们可以计算其他非基准位置,但必须首先找到所有的 Base Case。



根据我们的递归关系,Case 被迭代分解,知道满足 Base Case( j=0i=j )。由于我们知道这些 Base Case(1)的值,因此可以根据 Base Case 填充其他值。


当然,这是递归算法如何工作的极其详细的视图,可能过于详细了。实际上,这三个步骤都不需要编程;它们是通过脚本自动执行的。就实现方面而言,你需要做的就是调用函数本身,并确保它在某些时候必须在 Base Case 下终止。


当我们调用 return pascal(i-1, j) + pascal(i-1, j-1) 时,我们不会把返回看作一个过程,而是将它当做一个数字。由于 pascal(i-1, j) 会启动自己的分支过程,但最终会返回另一个数字(比如 3),因此将它视为后者而非前者是有帮助的,这可能会导致不必要的复杂性和令人头疼的问题。


人们可能会倾向于指出这种递归算法中的一些低效之处。毕竟, “6” 被分解为 “3”,这两个 “3” 具有相同的分解(就值而言),但它被天真地计算了两次。这在递归中很常见,在递归中,一个 Case 的 Base Case 已经计算过,但会再次计算。为了解决这一问题,我们使用记忆化。


以斐波那契(Fibonacci)数列为例,其中前两个数字是 0 和 1,下一个数字是前面两个数字之和。根据之前的知识,我们知道 Base Case 是 0 和 1,我们的递归关系是 v(i) = v(i-2) + v(i-1) 。因此,我们可以构造一个简单的递归函数来查找 斐波那契数列在任意索引 i 处的值,从 0 开始。



请注意,虽然这是递归的一个巧妙应用,但效率极其低下。 “8” 被分解为 “3” 和 “5”,而 “5” 又被分解为 “3” 和 “2”。我们从头开始计算所有内容,并建立一个完整的搜索树,但其中有很多重复项。



使用记忆化,我们就可以通过创建缓存来解决这个问题。这可以通过使用字典来实现,并存储我们以前看到过的值。例如,当索引 6(值为 8)被分为索引 4 和索引 5(值分别为 3 和 5)时,我们就可以将索引 4 的值存储到缓存中。当索引 5 被计算为索引 3 加上索引 4 时,我们可以从缓存中提取索引 4,而不是通过构建另一棵树向下扩展到 Base Case 来重新计算索引 4。为了将记忆化添加到我们的功能中,我们添加了两个功能:首先,如果当前索引已存储在缓存中,我们只需返回存储的值;其次,在我们继续减少之前,应该将值添加到缓存中,以便可以加快进一步的操作。请注意,缓存必须是全局变量,或者不管命令调用的范围如何,都可以进行检索和更改该变量。



通过添加简单的记忆化,我们的递归函数比以前任何时候都快得多,功能也更强大得多。


递归是各种最快排序算法的核心。排序算法的目的是收集一个数字列表,然后从最小值到最大值返回它们。由于许多应用程序都依赖于快速排序,因此寻找一种能够对列表进行最快排序的算法非常有意义。一些最快的算法使用分治法策略的递归方法。


分治法是一种策略,在这个策略中,出事问题递归地分解为多个子问题。在每个子问题具有单位大小(类似于 Base Case)之后,将为每个子问题找到子解,然后再次递归地将这些子解组合在一起,形成一个完整的解。



例如,考虑快速排序(QuickSort)是排序中最快的算法之一,如果实现得当,它的执行速度可以比它的竞争对手和前身快 2~3 倍。快速排序从选择一个 “基准” (Pivot)开始。在简单的实现中,就我们的目的而言,基准的选择是任意的,但更专业的实现对所选的基准非常谨慎。



所有小于基准的元素移到基准的左侧,所有大于基准的元素移到其右侧。请注意,这个做操只是部分地解决了这个任务。



通过其基准分割列表的过程称为分区,因为基准将列表华为两个分区或边。每个分区在自身上调用另一个分区迭代,以此类推,直到一个分区达到一个 Base Case(1 个单元,简单地说,就是一个数字)。



在执行足够的递归后,原始列表将被分割得足够多,以至于不能再调用递归。在这一点,子解的组成只是将他们横向堆叠在一起。组成的结果是一个排序的列表。


请注意,快速排序遵循前面讨论过的许多递归构建块,只是在更高级别上。递归关系是组件的分区,Base Case 是大小为 1 的分区。从一个原始列表开始,递归调用相同的进程(选择基准、分区),直到结果只包含 Base Case。

关键点

  • 递归是一种在函数内调用自身的编程方法,允许使用最少的代码进行循环和自动构建树。

  • 在构造任何递归函数时,必须清楚地理解两个元素:递归关系和 Base Case。

  • 记忆化是一种防止重复操作的方法,它将信息存储在缓存中,然后在需要时检索它们。

  • 分治法是递归的许多更深层次的应用之一,它将问题递归地分解为若干子问题(Base Case),从这些子问题中可以很容易地提取和聚合子解,从而形成一个完整的解。


作者介绍:


Andre Ye,Critiq 联合创始人,机器学习、计算机科学和数学爱好者,Medium 编辑、最佳作家。


原文链接:


https://towardsdatascience.com/advanced-concepts-in-recursion-every-effective-programmer-should-know-de233a092dbf


2020-08-14 08:001936
用户头像
刘燕 InfoQ高级技术编辑

发布了 1099 篇内容, 共 431.4 次阅读, 收获喜欢 1908 次。

关注

评论

发布
暂无评论
发现更多内容

Java的wait和notify学习三部曲之一:JVM源码分析

Java 程序员 后端

Java架构师面试问些什么?微服务之springcloud面试题(共22题

Java 程序员 后端

Java知识体系总结(2021版),JDK、JRE与JVM的区别与联系

Java 程序员 后端

Java注解-一文就懂,java程序设计与实践教程王薇

Java 程序员 后端

Java注解,java架构师课程哪家好

Java 程序员 后端

linux去掉空行的几种方法

入门小站

Linux

Java常量池理解与总结,java线程池回收原理

Java 程序员 后端

Java开发必备 Git 分支开发:规范指南及完全学会Git的24堂课笔记

Java 程序员 后端

Java程序员必须熟记的微服务面试题(含答案)

Java 程序员 后端

Java程序员的工资为什么那么高,首先要先掌握这999页阿里P8笔记!

Java 程序员 后端

Java程序员裸辞两个月,面试阿里、美团,值得一读

Java 程序员 后端

Flink 实践教程:入门(2):写入 Elasticsearch

腾讯云大数据

flink 流计算 Oceanus

033云原生之云服务测评指标体系

穿过生命散发芬芳

云原生 10月月更

java并发之Condition图解与原理剖析,推荐

Java 程序员 后端

Java并发之Condition详解,springframework教程

Java 程序员 后端

Java并发关键字-final,java实战视频

Java 程序员 后端

Java版流媒体编解码和图像处理(JavaCPP+FFmpeg)

Java 程序员 后端

文本行随机打乱工具

入门小站

工具

Java异常架构与异常关键字,海康威视java开发面经

Java 程序员 后端

Java是未来的第一编程语言吗?,3分钟告诉你为什么要用Java开发高频交易系统

Java 程序员 后端

Java架构师职位常见面试题,看完面试不再慌!

Java 程序员 后端

架构实战营第1期-毕业设计项目

Anyou Liu

「架构实战营」

Java程序员极力推荐的springboot全家桶干货系列

Java 程序员 后端

java程序员的AI之路-大数据篇 hadoop安装,java基础知识点梳理

Java 程序员 后端

Java日常开发的21个坑,你踩过几个?,java基础程序代码编写

Java 程序员 后端

java程序员的AI之路-大数据篇 hadoop安装(1)

Java 程序员 后端

Flink 实践教程:入门(1):零基础用户实现简单 Flink 任务

腾讯云大数据

flink 流计算 Oceanus

Java开发工作4年还是只会“增删改查”,java技术栈太广

Java 程序员 后端

Java架构师面试之Netty面试专题及答案(共10题,含详细解答

Java 程序员 后端

Java死锁的原因例子及解决方法,三年Java开发

Java 程序员 后端

Java程序员经典面试题集大全(一),分享面试经历的网站

Java 程序员 后端

每个高效程序员都应该知道的递归高级概念_AI_Andre Ye_InfoQ精选文章