Hola Nicolás,
Gracias por la aclaración, ahora se entendió mejor y me parece que el razonamiento está bien hecho, porque efecticamente lo que importa en este ejercicio para encontrar la cantidad de combinaciones son la cantidad de adoquines que separan la salida de la llegada y no la dirección en la que vas.
Sobre la pregunta que había quedado sin responder, no toda recursión general se puede llevar a recursión de cola. En la recusión de cola lo último que haces es el llamado recursivo. Si por ejemplo tenés una función que necesite hacer dos llamados recursivos no la podés llevar a recursión de cola.
Saludos