主页 / 问题 / 926108
Accepted
Makhmudov
Asked:2020-12-27 19:17:42 +0000 UTC2020-12-27 19:17:42 +0000 UTC

如何考虑递归？

  • 772

在特定算法领域有经验的程序员如何看待递归，他们如何看待它？

我解析快速排序，充当解释器，并开始对递归感到困惑。

def quick_sort(alist):
    if len(alist) <= 1:
        return

    barr = alist[0]
    left = []
    mid = []
    right = []

    for i in range(len(alist)):
        if alist[i] < barr:
            left.append(alist[i])
        elif alist[i] > barr:
            right.append(alist[i])
        else: #alist[i] == bar
            mid.append(alist[i]) 

    quick_sort(left) # Отсортировать левую часть
    quick_sort(right) # Отсортировать правую часть

    k=0
    for x in left+mid+right:
        alist[k] = x
        k+=1
    return alist

alist = [2,3,4,1]
print(quick_sort(alist))

在许多视频课程中，在一行代码中，当一个函数被自己调用时，老师引用该函数就好像它已经编写好了一样。

真的这么简单吗？你甚至不应该尝试像普通函数那样阅读递归函数。

如何在这个算法的上下文中阅读递归是特别有趣的！

PS。我知道递归的规则：从头开始阅读，基本情况，递归关系。

python

5 个回答

  1. Best Answer

    通过其调用树（eng.call stack tree）考虑任何递归函数很方便：

    在此处输入图像描述

    每个顶点都是一个函数调用点，而分支，奇怪的是，分支是一个递归调用。

    在代码中突出显示 2 点很重要：

    1. 断点
    2. 递归调用站点，或者换句话说，“分支站点”

    一般来说，它看起来像这样：

    def rec_func(...):
    if(stop_condition): <-- точка останова
        return ...

    rec_func(...) <-- ветвление
    rec_func(...) <-- ветвление

    return ... <-- "главный" return текущей вершины

    现在让我们从问题中分解快速排序：

    逻辑本身本质上非常简单：

    1. 根据某些标准划分数组，在该算法中，取决于枢轴的特殊值，直到获得单位长度的数组 - 单位长度的数组不能被取消排序。
    2. 从接收到的排序元素中收集一个数组

    秘诀在于第一段 - 你需要将数组分成两半关于某个元素，它通常称为枢轴。这个算法的断点也相当明显—— if(размер текущего массива <= 1)。

    在枢轴始终是最后一个元素的情况下，从所有这些我们得到这样的树：

    在此处输入图像描述

    您的代码始终使用第一个元素作为枢轴，但这不会改变算法的本质。

    所有没有后代的顶点都是我们正在寻找的单个数组，它们从左到右“连接”到最终数组中将是所需的排序数组。

    这棵树的每个顶点都是对分割该数组的递归函数的调用。

    枢轴和相等元素被写入“中央”数组，不需要排序或转移到某处。

    最后，回到斐波那契，我开始回答这个问题。这个算法的直线代码就像软木塞一样简单：

    def F(n):
    if n == 0: return 0   <-- точка останова
    elif n == 1: return 1 <-- точка останова
    else: return F(n-1)+F(n-2) <-- 2 точки ветвления, получаем бинарное дерево

    顺便说一句，用于计算斐波那契数的调用树说明了为什么递归对这种情况不利。树包含具有相同计算的整个分支。

    • 14

  2. 递归类似于归纳证明，数学家自己认为这是不明显的。

    因此，如果从第一次开始就不清楚递归，您只需要通过几个例子来考虑它。我会推荐使用树结构的示例，因为它们渲染得很好。

    让我们想象一棵二叉树。如果树很小并且由一个节点组成，那么它的高度等于 1。如果此节点有一个或两个子节点，则高度为 2。如何编写计算树高的程序？

    这就是递归派上用场的地方。首先，我们设定一般规则：二叉树的高度等于其子树高度的最大值的一加。

    int getHeight(BinaryTree binaryTree)
{
    int leftHeight = getHeight(binaryTree.left);
    int rightHeight = getHeight(binaryTree.right);

    return 1 + max(leftHeight, rightHeight);
}

    这样的函数并不完全正确，因为它永远不会停止并且会调用自己直到堆栈溢出。

    如果我们遇到退化的情况，我们可以阻止它。例如，我们可以认为空子树的高度为零，即getHeight(null) == 0。

    然后函数采用以下形式：

    int getHeight(BinaryTree binaryTree)
{
    if (binaryTree == null)
        return 0;

    int leftHeight = getHeight(binaryTree.left);
    int rightHeight = getHeight(binaryTree.right);

    return 1 + max(leftHeight, rightHeight);
}

    所以我们写了一个递归计算函数。这里重要的是区分递归函数的两个部分，它们与归纳证明相一致。

    第一部分：一般规则。我们的算法应该通过相同的计算来表达对某事物的计算，但结构更精细。第二部分：停止。在计算结束时，必须有一个退化的情况，它不是递归地考虑的，而是平凡的。假设一棵空树的高度为零。一的阶乘等于一。诸如此类的东西。

    另一个例子是算术表达式。让我们来看看：

    g * h * i + k ^ l ^ m

    尽管这个表达式看起来不像一棵树，但我们实际上可以将它表示为允许对其进行评估的树形形式。这是树的样子：

            +
    *       ^
  *   i   k   ^
g   h       l   m

    树的节点包含运算符，在我们的例子中，它们是加法+、乘法*和求幂^。子元素是其他表达式。

    计算表达式值的函数如下所示：

    double calculate(Expression expression)
{
    double left = calculate(expression.left);
    double right = calculate(expression.right);

    switch (expression.operator)
    {
        case '+':
            return left + right;

        case '*':
            return left * right;

        case '^':
            return pow(left, right);

        default:
            throw new Exception();
    }
}

    现在我们需要找到退化的情况来停止递归推理。这些是表达式是单个变量g或i. 这种表达式的值就是变量本身的值。假设对于我们对象中expression的此类变量，字段operator相等'v'，并且此类变量的值存储在关联数组中variables。然后函数看起来像这样：

    double calculate(Expression expression)
{
    if (expression.operator == 'v')
        return variables[expression.name];

    double left = calculate(expression.left);
    double right = calculate(expression.right);

    switch (expression.operator)
    {
        case '+':
            return left + right;

        case '*':
            return left * right;

        case '^':
            return pow(left, right);

        default:
            throw new Exception();
    }
}

    这个函数不是很好，因为在 OOP 语言中必须使用多态方法而不是switch. 但即使在 OOP 语言中，多态方法仍然会递归地相互调用。

    对于培训，一个不太正确但可以理解的选项适合我们。现在尝试自己解决递归问题，例如著名的河内塔问题。经过几次这样的任务，递归将不再有困难。

    • 6

  3. 我将给出一个编写一个简单的递归函数来解包带有注释的嵌套列表的示例，我希望它对某人有用：

    假设我们有一个列表，我们需要解包嵌套：

    t = [1, 2, [3, 4, [5]]]

    因此，我们开始编写一个函数，我将有一个列表作为输入：

    def extract(li):

    这里需要立即注意，既然结果是连接的，那就意味着你需要随身携带所有其他调用的结果，这意味着我们的结果应该在输入参数中，我们的答案是一个列表，嗯，让空列表为：

    def extract(li, result=[]):

    然后我们在这个例子中编写函数的主体，对元素进行循环：

    for i in li:

    现在到了分支步骤，在其中你需要确定函数调用自身的情况，对于这个例子，这个条件将检查元素是否是一个列表：

    if isinstance(i, list):
   extract(i, result)

    好吧，让我们定义一个普通的情况——这也是退出递归的一个选项，在这种情况下，退出递归调用是到达一个空列表或一个不是列表的元素：

    else:
    result.append(i)

    让我们用 command 结束函数return，我们开始和结束的地方是：

    return result

    全部的：

    t = [1, 2, [3, 4, [5]]]

def extract(li, result=[]):
    for i in li:
        if isinstance(i, list):
            extract(i, result)
        else:
            result.append(i)
    return result

print extract(t)
# [1, 2, 3, 4, 5]

    让我们给输入一些“东西”来看看函数的行为： 

    print extract([1, 2, [3, [], [5]]], [])
print extract([{}, 2, [[[[[[3]]]]]]], [])
# [1, 2, 3, 5]
# [{}, 2, 3]
    • 1

  4. 你太复杂了。不要挂断函数调用自身的事实。把函数想象成一个黑盒子。当你调用一个常规函数时，你不爬上去看看它是如何工作的吗？您只需要知道它需要什么作为输入以及它作为输出返回什么。以相同的方式处理递归函数，无论它是否仍在编写中。不要试图解开你脑海中的整个调用链。

    • 1

  5. 为了不挂在“Repeat”上，最好不是“从上到下”，而是“从下到上”，即从中断递归的结束条件开始探索递归。例如，最好从条件“如果 a==1，则返回 1”开始计算斐波那契数列，直到返回的数量等于所需的值。

    • 0

相关问题