Остановите убегающую рекурсию, чтобы заставить функцию Python работать правильно - PullRequest
Новая
       36

Остановите убегающую рекурсию, чтобы заставить функцию Python работать правильно

0 голосов
/ 28 сентября 2018

Я пытаюсь написать функцию, которая возвращает общую сумму произведений элементов в одинаковых позициях в двух списках с использованием рекурсии.Я пробовал различный код, чтобы остановить ошибку рекурсии (превышающую максимальную глубину рекурсии.) Можете ли вы помочь мне сделать эту функцию правильно?

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])

1 Ответ

0 голосов
/ 28 сентября 2018

Одна простая доработка вашего кода, чтобы он в основном работал, был бы: 

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, потому что ваши потенциальные данные превышали ~ 1000 пар - только позже я понял, что вы получили ошибку только с двумя элементами, так как ваш базовый случай вышел из строя.Итак, сначала я работал над большим количеством данных, чем размер стека:

Ниже приведен подход к увеличению предела длины списка с тысячи до четверти миллиона элементов.Мы не обойдем ограничение стека, а скорее разделим наше использование стека пополам, так что мы рекурсивно обрабатываем не более 500 списков по 500 элементов вместо одного списка из 1000 элементов: 

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 раз или более.

...