Python - convert recursion to a tail recursion

Question

To find the number of ways to get from one corner of a grid to the opposite corner, by going down or right only. I come up with an initial idea to use the recursion to solve the problem:

def find_num_of_ways(x: int, y: int):
    if x == 0 or y == 0:
        return 1
    return find_num_of_ways(x - 1, y) + find_num_of_ways(x, y - 1)

This can be stack overflow when x and y increase. Want to find a better way to refactor this, one is convert to tail recursion. But given 2 variables in the signature, so how to accumulate the result in order to make it tail recursion?

this will help [convert recursion to 'tail recursion'](https://stackoverflow.com/questions/15537432/convert-recursion-to-tail-recursion) — deadshot, Sep 11 '20 at 05:24
Tail recursion doesn't exist in Python. If there aren't any obstacles, you can compute this mathematically (Project Euler 15). If there are obstacles, use bottom up DP. — ggorlen, Sep 11 '20 at 05:38
@ggorlen well, of course tail recursion *exists* in python, but there is no tail-call optimization in CPython. — juanpa.arrivillaga, Sep 11 '20 at 05:43
OK, that sounds more technically correct but my point is that the stack will blow regardless of how you set up the code in CPython. Maybe another implementation optimizes it as a loop. — ggorlen, Sep 11 '20 at 06:01

cdlane · Answer 1 · 2020-09-11T07:00:07.903

My analysis of this is that it takes so long to compute an answer that you'll walk away long before the stack overflows. I'm going to suggest we remove the recursion altogether and do this as a boxes and balls combinatorial problem

(x + y - 1)!
------------
 y!(x - 1)!

plus the reverse:

(y + x - 1)!
------------
 x!(y - 1)!

that is, Python-wise:

from math import factorial as f

def find_num_of_ways(x, y):
    return f(x + y - 1) // (f(y) * f(x - 1)) + f(y + x - 1) // (f(x) * f(y - 1)) 

print(find_num_of_ways(10, 10))

OUTPUT

> python3 test.py
184756
>

Performance-wise, for the arguments:

find_num_of_waysTail(13, 14)

On my machine, the OP's original recursive solution takes 9 seconds, @Mike67's counter solution takes about 12 seconds, and my solution above takes about 0.05 seconds. All produce the result 20058300.

Mike67 · Answer 2 · 2020-09-11T06:46:46.753

Since all the paths end at the same point, you can just count how many times the last point is touched.

#### Recursion ####
def find_num_of_ways(x: int, y: int):
    if x == 0 or y == 0:
        return 1
    return find_num_of_ways(x - 1, y) + find_num_of_ways(x, y - 1)

ttl = find_num_of_ways(10,10)
print("Recursion", ttl)


#### Counter ####
ttl = 0
def find_num_of_waysCtr(x: int, y: int):
    global ttl
    if x == 0 or y == 0:
        ttl += 1
        return
    find_num_of_waysCtr(x - 1, y)
    find_num_of_waysCtr(x, y - 1)

find_num_of_waysCtr(10,10)
print("Counter  ", ttl)

Output

Recursion 184756
Counter   184756

Python - convert recursion to a tail recursion

2 Answers2