You could also do away with recursion altogether by applying dynamic programming. Start with an array of 3 values [1,2,4] for the possibilities of the first 3 steps and then calculate the following positions as the sum of the previous 3 positions in the array. The value at N - 1 is the number of possibilities.