How to improve this recursive function?

Question

How to improve this recursive function because its too slow. This problem is taken from project euler.

Problem:

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

MAX = 2
paths = 0

def a(x=0,y=0):
    if x==MAX and y==MAX:
        global paths
        paths+=1
        return
    if x>MAX or y>MAX:
        return
    a(x+1,y)
    a(x,y+1)
a()
print(paths)

It test all down and right until it reaches the last cell in the grid. In case it overlaps the grid, it will stop and move on to the next function in the call stack

Probably better asked on https://codereview.stackexchange.com/ — match, May 04 '20 at 13:24
Does this answer your question? [How to improve (speed, memory usage) search for unique number of paths to reach opposite corner algorithm?](https://stackoverflow.com/questions/61447315/how-to-improve-speed-memory-usage-search-for-unique-number-of-paths-to-reach) — Zabir Al Nazi, May 04 '20 at 13:27
reminder, cpython is not recommended for tail recursion https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion — SakuraFreak, May 04 '20 at 13:36
There are good and quick solutions on the forum of project euler itself. As said in one of the answer, there are a lot of other ways to do this better/faster. You are thinking too much in brute force. There is a lot to learn about latice paths on the internet, even on Wikipedia! — Wimanicesir, May 04 '20 at 13:38

score 3 · Accepted Answer · answered May 04 '20 at 13:45

This problem is the ideal candidate to apply the principles of dynamic programming using memoization as it contains overlapping sub-problems and optimal substructures. Your recursive solution is taking long time because it is spending most of its time in solving the same problem over and over again.

Use:

def find_paths(start, end, memo):
    if start == end:
        return 1
    elif start[0] > end[0] or start[1] > end[1]:
        return 0

    r_point, b_point = (start[0] + 1, start[1]), (start[0], start[1] + 1) 
    if not r_point in memo:
        memo[r_point] = find_paths(r_point, end, memo)

    if not b_point in memo:
        memo[b_point] = find_paths(b_point, end, memo)

    return memo[r_point] + memo[b_point]

Calling the function:

print(find_paths((0, 0), (2, 2), {}))
print(find_paths((0, 0), (20, 20), {}))
print(find_paths((0, 0), (100, 100), {}))

This prints:

6
137846528820
90548514656103281165404177077484163874504589675413336841320

Even though there are still better solutions that use more optimal formulas, I think this is the best way to solve it with recursion. — Wimanicesir, May 04 '20 at 13:50
I dont understand how my code is solving the same problem over and over unlike with the fibonacci. — beynDestroyer, May 04 '20 at 13:54
Suppose from (0, 0) you have moved down to (0, 1) and then you move right to (1, 1). Similarly in another case if you first move right (1, 0) and then move down to (1, 1). In both of those cases you will be solving the subproblem with a starting point as (1, 1) repeatedly. — Shubham Sharma, May 04 '20 at 13:57

Alain T. · Answer 2 · 2020-05-05T01:12:50.807

This is similar to Pascal's triangle. Reaching each point on the grid requires the sum of paths of the positions above and to the left up to the main diagonal (Pascal's progression) and then down to the destination.

2x2

Pascal's   Rest
*--1--1    *--1--1
|  |  |    |  |  |
1--2--+    1--2--3
|  |  |    |  |  | 
1--+--+    1--3--6  ==> 6 paths

3x3

Pascal's      Rest
*--1--1--1    *--1--1--1 
|  |  |  |    |  |  |  |
1--2--3--+    1--2--3--4
|  |  |  |    |  |  |  |
1--3--+--+    1--3--6--10
|  |  |  |    |  |  |  |
1--+--+--+    1--4--10-20 ==> 20 paths

4x4

Pascal's       rest        
*--1--1--1--1  *--1--1--1--1
|  |  |  |  |  |  |  |  |  |
1--2--3--4--+  1--2--3--4--5
|  |  |  |  |  |  |  |  |  |
1--3--6--+--+  1--3--6--10-15 
|  |  |  |  |  |  |  |  |  |
1--4--+--+--+  1--4--10-20-35 
|  |  |  |  |  |  |  |  |  |
1--+--+--+--+  1--5--15-35-70 ==> 70 paths

At this point, you could do more math or you could implement an efficient algorithm to compute the result:

N = 4
paths = [1]
for _ in range(N):
    paths = [ a+b for a,b in zip(paths,[0]+paths) ]+[1] # Pascal's
for _ in range(N):
    paths = [ a+b for a,b in zip(paths,paths[1:]) ]     # Rest
result = paths[0]

More Math: If you expand the square to 2N, you will also notice that the result is the point exactly in the middle of the main diagonal. This is the Nth value on line 2N of Pascal's triangle.

*--1--1--1--1··1··1··1··1  
|  |  |  |  |  :  :  :
1--2--3--4--5··+··+··8·· 
|  |  |  |  |  :  :
1--3--6--10-15·+··28··   
|  |  |  |  |  :
1--4--10-20-35·56·· 
|  |  |  |  |  
1--5--15-35-70··   <-- 70 is combinations of 4 in 8 
:  :  :  :    
1··+··+··56··
:  :  :    
1··+··28··
:  :    
1··8··
:   
1··

In accordance with properties of Pascal's triangle, this is equivalent to the number of combinations of N values in a set of 2N.

It can be calculated by (2N)! / N!^2: factorial(2*N)//factorial(N)**2

N=2 --> 4!/2!^2 --> 24/4 --> 6

N=3 --> 6!/3!^2 --> 720/36 --> 20

N=4 --> 8!/4!^2 --> 40320/576 --> 70

...

N=20 --> you do the math :)

Mikhail Vlasenko · Answer 3 · 2020-05-04T13:45:50.247

-1

There is a simple mathematical solution.

We need to make exactly 20 moves down, on any of the 40 positions we have (as it is always 20 down+ 20 right)

Therefore, the answer is 40 Choose 20 = 137846528820

How to improve this recursive function?

3 Answers3

2x2

3x3

4x4