Rewrite The Recursive Function Into Tail Recursive Function

Problem: Count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6. Solution: I have written a recursive solu

Solution 1:

One way for you to get around the stack overflow problem would be to simulate the callstack manually.

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))

Output:

16

Solution 2:

Here's a simple solution, no recursion, no nothing, 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

Result:

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

Easily can calculate the number of rolls for N=50000 or 500000.