аватар question@mail.ru · 01.01.1970 03:00

Использование рекурсии более 1000 раз

Я новичок в программировании на Python(мой 1 язык программирования). Решал задачу №12 из Проекта Эйлера. Я использовал рекурсию в функции, но к сожалению, чтобы решить задачу, придётся использовать рекурсию более 1000 раз. Хотел бы узнать, как решить эту задачу по-прежнему используя рекурсию, для того чтобы знать об этом в будущем.

Как можно улучшить код и что вы думаете о моих названиях переменных и функции?

Вот так звучит задача :

Последовательность треугольных чисел образуется путем сложения натуральных чисел. К примеру, 7-ое треугольное число равно 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять треугольных чисел:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Перечислим делители первых семи треугольных чисел: 1: 1 3: 1, 3 6: 1, 2, 3, 6 10: 1, 2, 5, 10 15: 1, 3, 5, 15 21: 1, 3, 7, 21 28: 1, 2, 4, 7, 14, 28 Как мы видим, 28 - первое треугольное число, у которого более пяти делителей.

Каково первое треугольное число, у которого более пятисот делителей?

Вот мой код:

def tringle_number(x):    if x == 1:        retu 1    else:        retu x + tringle_number(x-1)for i in range(1, 900):    a.append(tringle_number(i))print(a)need = 0all_number = [1]count = 0for item in a:    number = 0    for j in range(1, 100000):         if item % j == 0:            count = j            number += 1            if number == 100:                for items in all_number:                    need += 1                    if need == 1:                        all_number.append(item)                    else:                        continue         else:            continueprint(all_number[1])
аватар answer@mail.ru · 01.01.1970 03:00

По умолчанию размер стека в Питоне ограничен 1000 вызовов. Обычно этого достаточно. Если вы пишете рекурсивный алгоритм (вам так нравится, или вы портируете код с Lisp, или вы фанат ) то это ограничение может серьёзно испортить настроение.

Ограничение можно ослабить вызовом . Этот вызов увеличит предел, но он не всесилен. В Питоне количество вызовов ограничено ещё и количеством памяти которая выделена под стек. Изнутри программы повлиять на размер стека нельзя. Если стек переполняется, то операционная система останавливает интерпретатор.

Выбор грустный: или программа упрётся в лимит самого интерпретатора и получит исключение

RecursionError: maximum recursion depth exceeded in comparison

или программа будет остановлена с ошибкой

Segmentation fault (core dumped)

Во втором случае ничего сделать нельзя. В первом случае есть возможность восстановиться после ошибки - и это причина по которой это, вроде бы бесполезное, ограничение существует.

Для примера: на моей системе CPython ломается при глубине стека примерно 21817.

Если этого вам мало, то посмотрите . Он почти не использует аппаратный стек. На нем тоже нужно установить sys.setrecursionlimit. Я установил миллиард. Глубина рекурсии в 10 миллионов не проблема.

Для 100 миллионов не хватило 32GB памяти. В The Stackless Python один рекурсивный вызов занимает примерно 790 байт. 40 миллионов вызовов займут 32GB памяти.

Последнее ограничение преодолеть будет сложно. Если вам нужно больше, ищите другой интерпретатор (сообщите мне, как найдете) или другой язык (например с поддержкой оптимизации ).

Последние

Похожие