CODEWITHSUNDEEP
pythonalgorithmrecursionstack-overflowtail-recursion
Bharat Kul Ratan
Bharat Kul Ratan

Reputation: 1003

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

Upvotes: 0

Views: 348

Answers (2)

lenik
lenik

Reputation: 23498

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.

Upvotes: 0

Balaji Ambresh
Balaji Ambresh

Reputation: 5037

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

Upvotes: 1

Related Questions