Un ejemplo muy sencillo de entender... es la jerarquía de ficheros del PC...

Sabrás bien que una carpeta puede contener ficheros y otras carpetas. Y cada carpeta interna, igualmente puede contener más ficheros y más subcarpetas, y esas... lo mismo.
Entonces se plantea... cómo recorrer cada carpeta?. La recursividad simplifica enormemente el proceso de dicho recorrido.

Imagineos que se nos pide el tamaño total que ocupa una carpeta con todo su contenido...


Hay dos bucles dentro de esa función, el primero recorge el tamaño de cada fichero suelto en esa carpeta.
El segundo bucle recoge cada carpeta que mantiene la ruta... y como cada carpeta puede contener más carpetas y o ficheros, hace una llamada a la función que totaliza el contenido de dicha carpeta, que curiosamente es la misma función en la que está.
Eso es la recursividad, una función que directamente se llama a sí misma (o indirectamwente a través de otra).

Todo lo que tenga una estructura arbórea es factible de ser recorrido recursivamente, aunque hay más situacione en programación, por ejemplo al tratar con combinatoria, utilizar recursividad puede simplificar ciertas operaciones.

La recursividad debe limitarse a ser usado cuando es preciso, siempre que se pueda es preferible usar iteratividad, pero hay determinadas situaciones, en las que diseñar bucles iterativos es mucho más complejo que bucles iterativos.
El mismo ejemplo anterior utilizando bucles iterativos sería bastante más engorroso... puedes intentarlo, si quieres.

La recursividad usa una llamada a una función y toda llamada a una función exige guardar en la pila el estado actual. Y a la vuelta 'escupir fuera' lo que se guardó en la pila... esto supone un tiempo preciso para dicho proceso (las dos partes) y un consumo de memoria.
Que estos sea muy elevado o muy ligero va a depender exclusivamente de lo complejo de la función (cuántos datos deba guardar) y el nivel de profundidad de la recursividad...

...en el caso de ejemplo (de las rutas), puede estimarse despreciable desde el punto de vista 'humano', por que como ya he dicho el nivel de profundidad de anidamiento de carpetas está limitado en 32, pero lo normal es que ese nivel no se alcance más que pocas veces. De igual modo el número de parámetros para guardar y rescatar de la pila, son pocos. Pero ciertamente suele asumirse siempre que es así.

Cuando la recursividad sea indirecta y por tanto a través de una llamada externa que además exija un enlace en tiempo de ejecución, es cuando puede ser más lento. Pero esto no será muy frecuente...

Otra cosa a tener en cuenta es que un sistema que se presta a ser recursivo, intentar hacerlo iterativo, puede ser menos eficiente... el caso inverso es todavía más drástico, un sistema que se presta a ser iterativo hacerlo recursivo suele ser drásticamente menos eficiente. Por eso, cada caso debe hacerse con la forma natural que propiamente se expresa. Naturalmente dicho así, parece algo subjetivo cuando falta experiencia al programador, no lo es cuando se conocen las cosas a fondo.

En la compilación no hay diferencia apreciable. Puede haberlas debido a la optimización que el compilador quepa ahacer conforme al código que haya 'dejado' el programador, peor considerando las velocidades de procesamiento actual, no puede achacarse un tiempo de compilación diferente para cada caso (esto depende de la cantidad de código más que nada).