Перепишите рекурсивную функцию в хвостовую рекурсивную функцию

Question

Задача: подсчитайте количество способов построить сумму n, бросая кубик один или несколько раз. Каждый бросок дает результат от 1 до 6.

Решение: я написал для него рекурсивное решение, которое дает правильный ответ. Для больших значений n должно произойти переполнение стека. Поэтому я хочу избежать этого и переписать код, используя хвостовой рекурсивный подход. Вот мой код:

def numWays(n, arr):
  answer = 0
  for item in arr:
    if item <= n:
      if n == item:
        answer += 1
      else:
        answer += numWays(n-item, arr)

  return answer

li = [i for i in range(1,7)]
print(numWays(5, li)) #example n=5

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

Это также можно переписать как итеративную функцию, но я ищу общие способы преобразования рекурсивных функций в хвостовую рекурсию. Данная проблема, код и Python приведены только для примера. Ничего особенного c о тех.

Answer 1

Один из способов обойти проблему переполнения стека - смоделировать стек вызовов вручную.

def numWays(n, arr):
    call_stack = [(n, arr)]
    answer = 0
    while call_stack:
        n, arr = call_stack.pop(0)
        for item in arr:
            if item <= n:
                if n == item:
                    answer += 1
                else:
                    call_stack.insert(0, (n-item, arr))
    return answer


li = [i for i in range(1, 7)]
print(numWays(5, li))

Вывод:

16

Answer 2

Вот простое решение, без рекурсии, без ничего, O (N):

#!/usr/bin/env python

DICE = 6    # how many sides our dice has

rolls = [1]
for i in range(1,800) :
    rolls.append(sum(rolls[-min(i,DICE):]))

print rolls[:16]  # print results for the first 16 (zero-based!!)
print rolls[610]  # print result for 610 steps

Результат:

[1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617, 15109]
14527490260516100855695859704819627818108010882741117227956927412305738742399171256642436462028811566617818991926058940988565927870172608545709804976244851391054850231415387973537361

Легко рассчитать количество рулонов для N = 50000 или 500000.