时间戳

首页 > 解决方案 > 停止失控递归，使 Python 函数正常工作

python - 停止失控递归，使 Python 函数正常工作

问题描述

我正在尝试编写一个函数，该函数使用递归返回两个列表中相同位置的元素乘积的总和。我尝试了各种代码来停止递归错误（超过最大递归深度。）你能帮我正确地制作这个功能吗？

PS 必须使用递归！！

def dot(l1, l2):
if len(l1)==len(l2):

    newl1=l1[1:]

    newl2=l2[1:]

    else_dot = dot (newl1, newl2)

    if len(newl1) == 1:
         return l1[-1]*l2[-1]
return l1[0] * l2[0] + else_dot

dot([5, 3], [6, 4])

标签： pythonrecursionstack-overflow

解决方案

对代码进行一项简单的返工以使其基本运行是：

def dot(l1, l2):
    if len(l1) > 0 and len(l2) > 0:

        newl1 = l1[1:]
        newl2 = l2[1:]

        else_dot = dot(newl1, newl2)

        return l1[0] * l2[0] + else_dot

    return 0

print(dot([5, 3], [6, 4]))

虽然我们可能会做得更好。当我第一次阅读您的问题时，我以为您遇到了问题，RecursionError: maximum recursion depth exceeded因为您的潜在数据大于约 1,000 对 - 直到后来我才意识到您只有两个元素就出现了错误，因为您的基本情况不正常。所以，我实际上首先处理了比堆栈大小更多的数据：

下面是一种将列表长度限制从一千个元素提升到 25 万个元素的方法。我们没有绕过堆栈限制，而是将堆栈的使用分成两半，因此我们递归处理最多 500 个 500 个元素的列表，而不是一个 1,000 个元素的列表：

from random import randint
from sys import getrecursionlimit

LIMIT = getrecursionlimit() // 2  # use half the stack for each branch of recursion

def dot(l1, l2):
    len1, len2 = len(l1), len(l2)

    if len1 > 0 < len2:

        if len1 <= LIMIT >= len2:
            head1, *tail1 = l1
            head2, *tail2 = l2

            return head1 * head2 + dot(tail1, tail2)
        else:
            return dot(l1[:LIMIT], l2[:LIMIT]) + dot(l1[LIMIT:], l2[LIMIT:])

    return 0

a = [randint(1, 100) for _ in range(LIMIT * 200)]
b = [randint(1, 100) for _ in range(LIMIT * 200)]

# Two lists contain 100,000 random numbers from 1 to 100 for a result of ~250,000,000
# Python recursion limit is ~1,000 calls, so instead of hitting the limit at ~1,000
# list elements, we hit it just under 250,000 ((1000 // 2) ** 2) list elements.

print(dot(a, b))

调整sys.setrecursionlimit()，我们可以将限制增加 100 或 1000 或更多。

推荐阅读