时间戳

首页 > 解决方案 > 努力建立递归直觉

recursion - 努力建立递归直觉

问题描述

尽管我已经学习并能够理解一些递归程序，但我仍然无法像使用迭代一样轻松地使用递归获得解决方案。是否有任何课程或课程可用于建立递归直觉？怎样才能掌握递归的概念？

标签： recursion

解决方案

如果您想彻底了解递归的工作原理，我强烈建议您从了解数学归纳法开始，因为两者非常密切相关，甚至可以说是相同的。

递归是一种将看似复杂的问题分解成更小部分的方法。考虑阶乘函数的简单示例。

def factorial(n):
    if n < 2:
        return 1
    return n * factorial(n - 1)

例如，要计算factorial(100)，您只需要计算factorial(99)并乘以 100。这源于熟悉的阶乘定义。

以下是提出递归解决方案的一些技巧：

  • 假设您知道前一个递归调用返回的结果（例如，在计算factorial(100)时，假设您已经知道 的值factorial(99)。您如何从那里开始？）
  • 考虑基本情况（即递归何时停止？）

第一个要点可能看起来相当抽象，但它的意思是：大部分工作已经完成。你如何从那里去完成任务？在阶乘的情况下，factorial(99)构成了这一大部分工作。在许多情况下，您会发现识别这部分工作仅相当于检查函数的参数（例如n，在阶乘中），并假设您已经有了答案func(n - 1)。

这是另一个具体的例子。假设我们想在不使用内置函数的情况下反转字符串。在使用递归时，我们可能会假设string[:-1]或直到最后一个字符的子字符串已经被反转。然后，所需要做的就是将最后一个剩余的字符放在前面。使用这个灵感，我们可能会想出以下递归解决方案：

def my_reverse(string):
    if not string: # base case: empty string
        return string # return empty string, nothing to reverse
    return string[-1] + my_reverse(string[:-1])

综上所述，递归是建立在数学归纳之上的，这两者是密不可分的。事实上，可以很容易地证明递归算法使用归纳法起作用。我强烈建议您查看此讲座。

推荐阅读