主页 / 问题 / 1427216
Accepted
Сергей
Asked:2022-09-06 21:37:40 +0000 UTC2022-09-06 21:37:40 +0000 UTC

递归问题的简单解决方案

  • 772

在执行复杂的学习任务时（例如，在算法或数据结构上），许多人（包括我在内）由于使用递归而周期性地遇到问题。超出了允许的堆栈大小，或者程序运行的时间超过了条件允许的时间。在实际工作中，这将意味着程序运行缓慢或计算机资源使用效率低下。

同时，通过搜索找到避免此类问题的简单方法也不是很容易，文章更多是复杂的案例，你必须想出，在没有技巧的情况下，这可能不会很快。这里建议放一小部分简单的方法（最好是读者自己以答案的形式添加）。更好地关注 Python，但原则上大多数应该在逻辑上适用于许多编程语言。我想社区应该从知识库中受益。

алгоритм python

1 个回答

  1. Best Answer

    以下是 Python 中一些最简单的方法（很可能很容易移植到其他语言）。

    昨天在 Stepik 上解决问题的时候，我实际上都应用了所有这些（当然还有更复杂的例子，这里我简化了它以供读者理解），在其他情况下我使用了：

    1）如果允许递归深度有问题，如果你不摆脱递归本身：*

    您需要在代码中添加一行sys.setrecursionlimit (50000)- 括号中的参数在我所有的情况下具有如此大的值解决了这个问题（默认情况下，此参数为 1000 或略小，在下面的第一个示例中，当 时会出现错误a = 998） . import sys当然，还需要更多。

    我将重复最初的问题中所写的内容：“在实际工作中，这将意味着程序运行缓慢或计算机资源使用效率低下。” 除非绝对必要，否则最好不要使用它。

    * 超出递归深度时遇到的错误：

    RecursionError: maximum recursion depth exceeded in comparison和

    RecursionError: maximum recursion depth exceeded while calling a Python object

    2) 在函数结束时递归调用时：

    def test (a):
    a -= 1
    if a > 0:
        print (a)
    else:
        return
    test(a)


if __name__ == '__main__':
    a = 997
    test (a)

    我们可以在 的帮助while True下简单地重新制作函数，避免递归：

    def test (a):
    while True:
        a -= 1
        if a > 0:
            print (a)
        else:
            return

    3) 变体稍微复杂一点，函数中间有递归调用：

    def test(a, b):
    print ('test start, a, b', a, b)
    if a > 5:
        print('condition a')
        return test(a-1, b)
    if b < 5:
        print('condition b')
        return test(a, b+1)
    print ('test finish, a, b', a, b)


if __name__ == '__main__':
   a = 7
   b = 3

    您还需要添加continue和break避免递归，除了while True：

    def test(a, b):
    while True:
        print ('test start, a, b', a, b)
        if a > 5:
            print('condition a')
            a -= 1 
            continue
        if b < 5:
            print('condition b')
            b += 1
            continue
        print('test finish, a, b', a, b)
        break
    • 0

相关问题