Categories
程式開發

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


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

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

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

  • 递归的思维方式
  • 递归关系
  • 记忆化
  • 分治法策略

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

  • 一个或多个 Base Case(边界条件、基准条件),它们是终止条件(Terminating Case),在这些条件中,不需要用更多的递归来进一步寻找答案。
  • 一组规则(递归关系),通过启动另一轮递归,将其他条件减少到一个 Base Case。

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

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

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

原文链接:【https://www.infoq.cn/article/qDaE14JDP3Da1E9eVhoH】。未经作者许可,禁止转载。