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

Question

Я новичок в программировании на 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:
        return 1
    else:
        return x + tringle_number(x-1)
for i in range(1, 900):
    a.append(tringle_number(i))
print(a)

need = 0
all_number = [1]
count = 0
for 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:
            continue
print(all_number[1])

Answer 1

рекурсия реализуется вызовом функции из самой себя

любой вызов функции, ее исполнение и выдачу результата выглядит так:

записать адрес точки возврата в стек
перейти в начало функции
выполнить функцию
извлечь из стека последнее число (адрес) и перейти по нему

когда выполняется рекурсия, то в стек пихаются адреса точки возврата и не выпихиваются обратно (пока рекурсия не опустится на самый глубокий уровень)

в определенный момент стек просто переполняется (поскольку не резиновый)

поэтому говорить "как сделать рекурсию без рекурсии" не очень корректно -

ответ такой - ОТКАЖИТЕЛЬ В ДАННОЙ ЗАДАЧЕ ОТ РЕКУРСИИ

P.S.

вот код без рекурсий (работает довольно быстро):

def count_dividers(value):
    count = 1

    dividers = set()

    for i in range(1, 2 + int(value**0.5)):
        if value % i == 0:
            if i not in dividers:
                dividers.add(i)
                dividers.add(value // i)

                count += 1 if i * i == value else 2

    return count


index = 1
while True:
    # получить треугольное число
    num = (1 + index) * index // 2
    index += 1

    # определить кол-во делителей числа
    if count_dividers(num) > 1000:
        print(num, index)
        break

вот этот код подсчета делителей более оптимальный (меньше проверок и действий):

def count_dividers(value):
    count = 0
    limit = math.floor(value**0.5)

    for i in range(1, limit + 1):
        if value % i == 0:
            count += 2

    count -= 1 if limit * limit == value else 0

    return count

Answer 2

выполняется он конечно очень долго

for i in range(1, 900):
    a.append(tringle_number(i))

Подумайте, что здесь происходит. Что делает функция tringle_number, когда она вызывается с аргументом 898 и с аргументом 899.

Answer 3

я бы сделал так:

import functools

@functools.lru_cache
def tringle_number(x):
    if x == 1:
        return 1
    else:
        return x + tringle_number(x-1)

def f(n):
    number = 0
    for i in range(2, n + 1):
        if n % i == 0:
            number += 1
    return number
    
    
a = []
for i in range(1, 900):
    a.append(tringle_number(i))

for item in a:
    if f(item) >= 100:
        print(item)
        break

Answer 4

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

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

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

RecursionError: maximum recursion depth exceeded in comparison

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

Segmentation fault (core dumped)

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

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

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

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

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

БЛОГ НА HUSL

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

Ответы (4 шт):