USACO problem - hopscotch Part 1

Problem using recursion.

Recursion is when a function calls itself over and over again, and is used in both math and programming.

I.e. in fibonacci sequence, f(x) = f(x-1) + f(x-2)
It is calling its last two numbers and adding them to get the current position.

In this problem, we recursively find the sum of the ways we can reach our destination. However, this is NOT fast enough (!)  to solve this problem, there is a better way I will show later, called dynamic programming.

Problem From:
http://www.usaco.org/index.php?page=viewproblem2&cpid=530

Psuedocode:
function cowhop (CurrentRow, CurrentColumn, lastLetter):

       sum = 0

       for i: CurrentRow->R-1:
            for j: CurrentColumn->C-1 :
if grid[i][j] != lastLetter:
sum = sum + cowhop(i,j, oppositeLetterOf(lastLetter) )

if grid[CurrentRow][CurrentColumn] != grid[R][C]:
sum = sum + 1 
        
return sum

(Note: for simplicity of non-coders, I started the indicies of array "grid"  from 1, not 0! )
(Note also the grid is 0,0 from top left and 4,4 on bottom right. Not your normal coordinate system)
How it works:

We give in a value of CurrentRow and CurrentColumn for each run. (The base case is (R=1,C=1))
Then we search any values that are different from CurrentRow,CurrentColumn to R-1,C-1.

The reason for skipping far right/far bottom is we have to be minimum one down AND one right to make valid jump. If we are already far down, we can't go down anymore!

There are four: 3,2,2,4. We don't bother searching on the last row or the farthest right row because there aren't anything more down or more right; we have to jump to a square at least one down AND one right.

We start from the first one, and do cowhop(2,2). We land on a "3".

We only have the "4" to search, and it is in fact different from the original "3". So we search "4" and run cowhop(3,3).

The only way to go is to the end, grid[R][C], which is 1.

This means cowhop(3,3) has returned a value of 1.

Tracing back,  we see if cowhop(2,2) has any more to search. Nope, so back. 

We will  carry the value of 1 from cowhop(3,3) to this cowhop(2,2), as we can go from (2,2) to (3,3). Note it is also different than the last one, so we can go down, adding one to total sum. 

Cowhop(2,2) will return a sum of 2.

Tracing to the farthest back, from cowhop(3,3) = 1 -> cowhop(2,2) = 1+1 = 2 -> cowhop(1,1).

We also add the 2 to the sum of cowhop(1,1), so for now, there are two ways.

But(1,1) still has more ways! There are 2,2,4 to search from, we only did "3"!

We will start with 2, since it is the next one.  We will continue diving deeper into the grid and back tracing until this:

Our final answer is 5.