Una función recursiva es una función que se llama a sí misma... las dudas que se le plantean al programador es ¿cuándo y cómo se paran? La respuesta fácil es poniendo una condición, exactamente igual que en un bucle. Poner mal una condición en un bucle acarrea los mismos efectos que poner mal una condición en una función recursiva, los mismos: repetición infinita, sobrecarga de la memoria y el procesador, en fin, un completo desastre.

Por poner un ejemplo, voy a poner el código en erlang que calcula el factorial de un número... El mismo ejemplo que te puedes encontrar en siene' y siene' de libros sobre cualquier lenguaje cuando se explican las funciones recursivas, no voy a ser original en ésto.

factorial(X) ->
    case X of
      0 -> 1;
      X -> X * factorial(X-1)
    end.

Son cinco líneas fáciles de entender:

1. Definición de la función con el nombre factorial que recibe un sólo parámetro X. Los caracteres -> indican que a partir de ahí comienza el cuerpo de la función que finaliza en el carácter ..
2. La siguiente línea utiliza la estructura case ... of que es idéntica a la switch...case a la que estás acostumbrado. Se le pone el parámetro X para que compruebe su contenido.
3. En este caso el contenido es 0 y es importante entender que ésta es la condición de escape de la recursión. Si hubiéramos hecho una función con bucle, seguramente sería algo como while (X!=0). Los caracteres -> indican el cuerpo de la condición, que en nuestro caso se limita a devolver 1 y el cuerpo de la condición finaliza con el carácter ;.
4. En esta línea se contempla el caso para cualquier valor de X. También tiene su bloque de código. En este caso se le pide que multiplique X por el resultado de factorial pasándole el valor de X-1. Esta es la línea que hace la recursión y actualiza el contador a la vez. En una función con bucle, tienes que actualizar el valor del índice también.
5. Línea de finalización del bloque de código. Si te fijas, en la línea anterior no pusimos ; y eso es porque al terminar con end el case...of acaba también el bloque anterior. Por último, como dije antes el . finaliza la definición del bloque de código de la función.

Una forma más simplificada de la función sería:

factorial(0) -> 1;
factorial(X) -> X * factorial(X-1).

Una de las idiosincrasias de erlang que nos proporciona una sintaxis más cercana a las condiciones como se expresan en matemáticas, cuando veíamos teoremas y similares y nos decían cosas tan bonitas como: Para todo x igual 0 y perlas similares. Aunque en este caso tendríamos que aplicarnos la definición de para todo X, cuando X es mayor que 0... porque no hay factoriales de números negativos. La cosa quedaría así.

factorial(0) -> 1;
factorial(N) when N > 0 -> N * factorial(N-1).

Pero bueno, estos son cosas del erlang. En Pyton lo solucionarías con un if. Explico esto, para se entienda mejor el siguiente apartado, porque esta forma de definir funciones y comprobar qué parámetros le llegan es una idiosincrasia del lenguaje.

Hay otra forma de recursión que se utiliza para simplificar condiciones y aplanar el espacio de memoria y proceso que conlleva la recursión. Lo que hace es contar el número de veces que aparece un elemento en una lista. Por poner un ejemplo real, voy a poner aquí código que hice para resolver un problema para un programa que estoy haciendo:

%%--------------------------------------------------------------------
%% @doc
%% Dada una Lista de elementos, cuenta el número de veces que aparece
%% y devuelve una lista de tuplas ordenada de mayor a menor número de
%% apariciones, donde cada elemento de la tupla consta de dos
%% elementos, el primero es el valor buscado de la Lista original y el
%% segundo el número de veces que aparece en ella.
%% @end
%%--------------------------------------------------------------------
contar_elementos(Lista) ->
    %% Nos apoyamos en la función recursiva contar_elementos/2
    contar_elementos(Lista, #{}).

contar_elementos([H|T], X) ->
    case maps:is_key(H,X) of
        true ->
            %% Si el elemento H existe en X suma 1 a su valor
            contar_elementos(T, maps:put(H, maps:get(H,X) + 1, X));
        false ->
            %% Si el elemento H no existe en X lo crea con valor 1
            contar_elementos(T, maps:put(H, 1, X))
    end;
contar_elementos([],X) ->
    %% Si no hay más elementos convierte X en lista y la ordena
    R = maps:to_list(X),
    lists:sort(
      fun({_,N},{_,M}) ->
              N > M
      end,
      R).

En la sintaxis de erlang son dos funciones distintas: contar_elementos/1 y contar_elementos/2, es decir, una función recibe un parámetro y otra función ─con el mismo nombre─ recibe dos parámetros y son funciones completamente distintas. La primera termina en un . tras llamar a la segunda, que tiene dos partes, o dos condiciones, o dos casos. Es decir, la primera utiliza una función recursiva como función auxiliar para hacer su trabajo. Y como es un ejemplo de la vida real, aunque sea corto, hay tela que cortar:

cortar_elementos(Lista, #{})

Esta línea hace la llamada. Como se puede ver le pasa a la función auxiliar la Lista que ha recibido y un elemento que podemos llamar acumulador: #{}. Ese símbolo equivale a pasar un map vacío. En Python se llaman diccionarios. La utilidad de éste parámetro es ir guardando los resultados del procesamiento de la lista.

contar_elementos([H|T],X) ->

Definición de la función contar_elementos/2 para el caso en que llega una lista ([H|T]) y X como parámetros. [H|T]. Todo lo que va entre los caracteres [...] definen una lista². En este caso dividida en las partes H y T³. Es decir, que definiendo así la entrada, en realidad me aprovecho de tres parámetros aunque la función reciba sólo dos, porque troceo el primero.

case maps:is_key(H,X) of

Aprovecha el troceamiento que hemos hecho de la lista al llegar y lo que hace es utilizar una función de los maps que nos dice si una clave H está en una lista X. Los valores que devuelve son sí o no: true o false. Por eso en el case hay dos bloques de código, uno para cada una de las respuestas posibles.

• contar_elementos(T, maps:put(H, maps:get(H,X) + 1, X));: Quizá te resulte más claro si lo hacemos por partes:

  Valor = maps_get(H,X),
  Diccionario_actualizado = maps:put(H, Valor+1, X),
  contar_elementos(T, Diccionario_actualizado);
  

  Es decir, toma el Valor existente, obtiene un diccionario actualizado sumándole 1 al Valor asociado a la clave H y llama de nuevo a la función con el resto de elementos de la lista T y dicho diccionario actualizado.

• contar_elementos(T, maps:put(H, 1, X)): Básicamente es lo mismo pero en este caso, como no se ha encontrado el elemento de clave H lo que se hace es crearlo con el valor 1... lo podríamos separar también como:

  Diccionario_actualizado = maps:put(H,1,X),
  contar_elementos(T, Diccionario_actualizado)
  

contar_elementos([],X) ->

La segunda parte de la definición de la función: cuando la lista se ha vaciado... (parámetro [], lista vacía). Es decir, hemos alcanzado el final de la lista, no hay más elementos en la cola para procesar. La forma directa hubiera sido devolver X y hemos terminado. Sin embargo, me faltaban un par de detalles por hacer: convertir el diccionario en una lista y devolverla ordenada de mayor a menor.

R = maps:to_list(X),

Es una función de la librería de maps de erlang que devuelve una lista a partir de un map o diccionario.

(no term)

Ordenar la lista y las funciones lambda:: El siguiente bloque de código ordena la lista que obtuvimos en el paso anterior:

lists:sort(
  fun({_,N},{_,M}) ->
          N > M
  end,
  R).

Utilizamos la función sort de la librería lists de erlang. Esta función ordena una lista tomando como parámetro una función que determina qué elemento es mayor (o menor, según nos interese el orden) que otro. En este caso está definida dentro de la propia llamada al más puro estilo lambda de lenguajes como Lisp, scheme y también las encontrarás (si no las has visto ya) en Python. En este caso indica que dados dos grupos de datos formados por tuplas del estilo {Índice, Valor}, será mayor la que posea un Valor mayor... el carácter _ le indica a erlang que hay algo, pero que puede ignorarlo porque no es relevante.

Quizá te hayas perdido en las explicaciones sintácticas. Necesitamos un resumen de lo que viene a ser el tema recursivo sobre las listas. Veamos un ejemplo alejado de la programación.

Hace años se vendían las legumbres al peso... ibas a la tienda de ultramarinos pedías lentejas y el dependiente salía con una paleta, hacía un cucurucho de papel y lo llenaba con las lentejas que cogía de un saco de bordes que habían enrollado hasta que se pudiera ver el género. ¡Lentejas pardinas de calidad, señora!... El caso es que llegaba un momento en que querías comértelas y lo habitual es que hubiera que limpiarlas: quitar piedrecitas, ramitas y otros elementos extraños a lo que vienen siendo las lentejas, propiamente dichas.

Como puedes imaginar, en este ejemplo nuestra lista es el montón de lentejas que tenemos recién comprado y ahora vamos a procesarla: cogemos un elemento del montón, si es una piedra o elemento extraño va al montón de la basura, si es una lenteja va al montón de las lentejas limpias. Proceso repetitivo que se ajusta a nuestros parámetros de cabeza y cola: tomamos un elemento, decidimos sobre su naturaleza y repetimos.

Con el procesamiento de listas es sencilla esa recursión de cabeza y cola. Ahora imagina que en el ejemplo anterior de la lista de números, hubiéramos cogido el sistema de coger el número y compararlo con el resto de los valores de la lista para contar cuántos hay. Sería como coger una lenteja (o piedra) y compararla con el resto de elementos del montón antes de llevarlo a su sitio. Si hay 500 lentejas tendrías que repasar el montón 499 veces cada vez... un procesamiento ineficiente. Por eso, cuando limpiamos lentejas repasamos el montón sólo una vez.

No hay que asustarse con este tipo de funciones.

Repasar un montón de elementos se puede hacer de dos maneras: recursiva o repetitivamente. En realidad, ambas, repasan todo el montón, desde la primera lenteja a la última. Tienes que recodar que repasar el montón con cada lenteja es tontería y lo demás es secundario. Elegir un método u otro depende también del lenguaje y de las costumbres del programador. Además, como digo siempre, si funciona está bien y si lo hace rápido es excelente. Lo de la elegancia del código siempre es una apreciación subjetiva.

Recuerda, las estructuras para hacer una reiteración o para hacer una recursión son las mismas: una variable donde guardar los cálculos⁴, un contador o una condición de final y en cada vuelta hay que actualizar el contador. En el caso especial de la lista, el contador son los mismos valores de la lista, por el mecanismo cabeza y cola.