0

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 solution for it which outputs correct answer. For large values of n it should hit stack overflow. So I want to avoid it and rewrite the code using tail recursive approach. Here's my code:

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

I've seen example of writing factorial function as tail recursive on web but that was easy. Not able to apply that accumulator trick to store the required answer as an additional argument in the function call. Are there any other tricks which work in general?

This could be rewritten as iterative function also but I am looking for ways in general to convert recursive functions to tail-recursive. The given problem, code, and Python is just for an example. Nothing specific about those.

Bharat Kul Ratan
  • 985
  • 2
  • 12
  • 24
  • Have you seen this [post](https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion#13592002) on why tail recursion doesn't matter in python and a way for you to set the max level of recusison? – Balaji Ambresh May 29 '20 at 11:55
  • @BalajiAmbresh: actually my focus is to rewrite recursive into tail-recursive. I originally wrote it in Scala but Python is more well-known so used it as an example here. – Bharat Kul Ratan May 29 '20 at 12:01
  • Can you clarify what "ways to construct the sum n" means? In particular "sum n" – ePi272314 May 29 '20 at 12:16
  • @ePi272314: For example, if n=3, there are 4 ways: a)1+1+1 b)1+2 c)2+1 d)3 – Bharat Kul Ratan May 29 '20 at 12:19

2 Answers2

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
Balaji Ambresh
  • 4,977
  • 2
  • 5
  • 17
0

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.

lenik
  • 23,228
  • 4
  • 34
  • 43
  • Thanks. But I actually want to learn how to change recursive functions into tail recursive in general. Used the problem, code, and Python just for example so that question doesn't become too theoretical. May be I should mention this in question specifically. – Bharat Kul Ratan May 29 '20 at 12:10