Runtime of a recursive algorithm
By no means, no, your solution is not linear. It is exponencial, O(2^max(x,y)). You can see in your own picture: each function call makes another 2 calls, and that stacks multiplicatively.
Now, for memoization, you would probably build a matrix and keep the records on it, in such a manner that a i,j iteration will rely only on already made calculations on x,y iterations, where x &lt;= i and y &lt;= j. This will probably result into something like O(xy), if no further calculations are made per iteration. 

Finally, are you sure about this problem? It is rather a combinatorial problem that does not involve any algorithm. The problem can rephrased as: how many different permutations one can get from the following string:

RRRRDDD

Where R appears x times, and D y times? This is merely a permutation with repetition: http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm