what is the difference of these two implementations of a recursion algorihtm?

Question

I am doing a leetcode problem.

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

So I tried this implementation first and got a "exceeds runtime" (I forgot the exact term but it means the implementation is slow). So I changed it version 2, which use a array to save the results. I honestly don't know how the recursion works internally and why these two implementations have different efficiency.

version 1(slow):

class Solution {
   // int res[101][101]={{0}};
public:
    int uniquePaths(int m, int n) {
        if (m==1 || n==1) return 1;
        else{ 
            return uniquePaths(m-1,n) + uniquePaths(m,n-1);
        }
    }
};

version2 (faster):

class Solution {
    int res[101][101]={{0}};
public:
    int uniquePaths(int m, int n) {
        if (m==1 || n==1) return 1;
        else{ 
            if (res[m-1][n]==0) res[m-1][n] = uniquePaths(m-1,n);
            if (res[m][n-1]==0) res[m][n-1] = uniquePaths(m,n-1);
            return res[m-1][n] + res[m][n-1];
        }
    }
};

From a quick glance, the second seems just to be https://en.wikipedia.org/wiki/Dynamic_programming . It does not compute results twice. Add `System.out.println("Call with "+m+" and "+n)` at the beginning of both methods, and try it with small inputs. You'll see the difference. Also see http://stackoverflow.com/a/25665931/3182664 — Marco13, Jun 26 '16 at 20:24

score 1 · Accepted Answer · answered Jun 26 '16 at 20:39

Version 1 is slower beacuse you are calculating the same data again and again. I'll try to explain this on different problem but I guess that you know Fibonacci numbers. You can calculate any Fibonacci number by following recursive algorithm:

fib(n):
if n == 0 then return 0
if n == 1 then return 1
return fib(n-1) + fib(n-1)

But what actually are you calculating? If you want to find fib(5) you need to calculate fib(4) and fib(3), then to calculate fib(4) you need to calculate fib(3) again! Take a look at the image to fully understand:

The same situation is in your code. You compute uniquePaths(m,n) even if you have it calculated before. To avoid that, in your second version you use array to store computed data and you don't have to compute it again when res[m][n]!=0

what is the difference of these two implementations of a recursion algorihtm?

1 Answers1