Почему код разбиения на слагаемые не работает?

Question

[Canp]

Разбиение на слагаемые числа 5 согласно статьи с кодом должно выдать 2+1+1, а выдает только количество слогаемых 3.

Как вывести на принт сами слагаемые?

Почему когда я указываю большие разбиваемого и количества слогаемых,вылетает ошибка:

print(partition(1024,5))

вывод:

Traceback (most recent call last):
File "/data/user/0/ru.iiec.pydroid3/files/accomp_files/iiec_run/iiec_run.py", line 31, in
start(fakepyfile,mainpyfile)
File "/data/user/0/ru.iiec.pydroid3/files/accomp_files/iiec_run/iiec_run.py", line 30, in start
exec(open(mainpyfile).read(), __main__.__dict__)
File "", line 19, in
File "", line 13, in partition
File "", line 13, in partition
File "", line 13, in partition
[Previous line repeated 992 more times]
File "", line 6, in partition
RecursionError: maximum recursion depth exceeded in comparison

[Program finished]

def partition(n, k, memo=None):
    if memo is None:
        memo = {}
    if (n, k) in memo:
        return memo[(n, k)]
    if n == 0 and k == 0:
        return 1
    elif n == 0 or k == 0:
        return 0
    elif n < k:
        return partition(n, n, memo)
    else:
        memo[(n, k)] = partition(n - 1, k - 1, memo) + partition(n - k, k, memo)
        return memo[(n, k)]
 

print(partition(5,3))

Comments

[Модератор]

Когда вы регистрировались, вы обещали выполнять Регламент.

В процессе создания вопроса пользователь Сервиса обязан:
3.6. Соблюдать нормы русского языка и принципы построения вопросительных предложений.

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

Если вы будете продолжать нарушать Регламент, ваши вопросы могут быть удалены, а аккаунт заблокирован модераторами временно или навсегда.
Будьте благоразумны.

Answer 1

[Михаил Р.]

Почему когда я указываю большие разбиваемого и количества слогаемых,вылетает ошибка:
print(partition(1024,5))

Превышено количество рекурсивных вызовов в Python.

Можно увеличить глубину рекурсий:

import sys
sys.setrecursionlimit(5000)

Либо, переписать функцию в итеративном стиле:

def partition(n, k):
    stack = [(n, k, [])]
    while stack:
        current_n, current_k, current_partition = stack.pop()
        
        if current_n == 0 and current_k == 0:
            print(" + ".join(map(str, current_partition)))
        elif current_n == 0 or current_k == 0:
            continue
        elif current_n < 0:
            continue
        else:
            for i in range(1, current_n+1):
                new_n = current_n - i
                new_k = current_k - 1
                new_partition = current_partition + [i]
                stack.append((new_n, new_k, new_partition))

partition(5, 3)

Comments

[Canp]

Большое Спасибо !!!

Answer 2

[Сергей П]

Во-первых, "слагаемые".
Во-вторых, почитайте код вашей рекурсивной функции, он выдаёт количество, а не сами варианты сложения. Если не можете это понять из кода, то вам рано такие задачи. Серьёзно.
А ошибка у вас из-за того, что такой алгоритм упирается в размер максимальной глубины рекурсии. Если хотите такие значения считать, делайте итеративный алгоритм, а не рекурсивный. Если эти слова тоже для вас новые, то надо браться за учебник, эта задача слишком сложна будет для вас.
Успехов.