hola emiliano,
lo primero es que podrías hacer un manejo menos complicado del valor de caminos: en el caso base asignarle 1 y en el recursivo 1 + ...
lo segundo es que en la llamada recursiva sólo consideras los caminos restantes habiendo avanzado (te quedan n-1 baldosas por delante). seguís sin considerar la opción de saltar.
saludos