Как ускорить рекурсию на python?

Вы можете использовать functools для этого:

import functools

with open('input.txt', 'r') as y:
    num = int(y.readline())
    @functools.lru_cache(maxsize=None)
    def recurs(cycle, num):
        if num == 0:
            return 1
        c = 0
        for i in range(1, cycle):
            if num - i < 0:
                break
            c += recurs(i, num - i)
        return c
with open('output.txt', 'w') as f:
    f.write(str(recurs(num + 1, num)))

немного измененный способ gord1402, который работает чуть побыстрее (проверял на N = 1000):

@functools.lru_cache(maxsize=None)
def recurs(cycle, num):
    return 1 if num == 0 else sum(recurs(i, num - i) for i in range(1, min(cycle, num + 1)))

вот так еще чуть-чуть побыстрее:

@functools.lru_cache(maxsize=None)
def recurs(cycle, num):
    if num == 0:
        return 1
    c = 0
    for i in range(1, min(cycle, num + 1)):
        c += recurs(i, num - i)
    return c

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

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

Например, имея 9 кубиков можно построить 5 разных лесенок шириной не более 6. Для этого возьмем все лесенки, которые можно построить из этих кубиков, но с меньшей шириной (не более 5)

А после отложим 6 кубиков для основания, и из оставшихся сложим все возможные лесенки, опять же с меньшей шириной

и положим их на это основание

Получим 5 лесенок из 9 кубиков с шириной основания не больше 6

И для этого достаточно будет сложить всего два значения - количество лесенок из 9 кубиков с шириной не больше 5 и количество лесенок из 3 кубиков шириной не больше 5

Делать это рекурсивно с кешированием или таблично – решайте сами.

_{Тонкий момент: да, из нуля кубиков можно построить одну лесенку нулевой ширины – пустую лесенку.}

немного считирил чтоб написать более быстрый алгоритм:

1. сгенерировал первые несколько членов последовательности

    1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113,
   

и отправил их в wolfram alpha, чтоб посмотреть, будет ли найдена аналитическая формула

2. была найдена к сожалению только рекурентная:

https://www.wolframalpha.com/input?i2d=true&i=1%5C%2844%29+1%5C%2844%29+2%5C%2844%29+2%5C%2844%29+3%5C%2844%29+4%5C%2844%29+5%5C%2844%29+6%5C%2844%29+8%5C%2844%29+10%5C%2844%29+12%5C%2844%29+15%5C%2844%29+18%5C%2844%29+22%5C%2844%29+27%5C%2844%29+32%5C%2844%29+38%5C%2844%29+46%5C%2844%29+54%5C%2844%29+64%5C%2844%29+76%5C%2844%29+89%5C%2844%29+104%5C%2844%29+122%5C%2844%29+142%5C%2844%29+165%5C%2844%29+192%5C%2844%29+222%5C%2844%29+256%5C%2844%29+296%5C%2844%29+340%5C%2844%29+390%5C%2844%29+448%5C%2844%29+512%5C%2844%29+585%5C%2844%29+668%5C%2844%29+760%5C%2844%29+864%5C%2844%29+982%5C%2844%29+1113%5C%2844%29

3. которую я и закодил

код:

import sys
sys.setrecursionlimit(10000)

import functools
@functools.cache
def a(n):
    if n == 0:
        return 1
    else:
        a_sum = sum([sigma(k) * a(n - k) for k in range(1, n + 1)])
        b_sum = 2 * sum([sigma(k) * a(n - 2 * k) for k in range(1, n // 2 + 1)])
        return (a_sum - b_sum) // n


@functools.cache
def sigma(n):
    return sum([i for i in range(1, n + 1) if n % i == 0])

В итоге для N = 1000 скорость возросла в 25 раз и время выполнения уменьшилось с 6,4 сек, до 0,25 сек :)

Ну и главный недостаток - требование к длине рекурсий увеличенное - так что пришлось повышать предел через sys.setrecursionlimit(10000)