[joker99]

а так?

int NumberOfRoutes = 0;
function void countRoutes(int cur)
{
    if (cur == N)
    {
      NumberOfRoutes++; 
      return;
    }
    if(cur+1<=N)
      countRoutes(cur+1);
    if(cur+2<=N)
      countRoutes(cur+2);
    if(cur+3<=N)
      countRoutes(cur+1);
}

Запускать countRoutes(0)