Soy débil, lo reconozco. No se decirle que no a los imperativos de una dama, tal vez por un primitivo impulso machista de querer impresionar y mostrarme como «el que todo lo soluciona», pero eso lo dejo en manos de psicoanalistas. El caso es que me han pedido que explique la recursividad en la programación, y para qué voy a explicarlo a una sola persona si puedo ponerlo aquí y que lo lea todo el que lo necesite (aunque la verdad, si lo buscáis en Google hay miles de ejemplos).

La recursividad es un recurso (qué «rebuznante» suena ponerlo así) muy potente a la hora de programar. Una función recursiva no es otra cosa que una función que se define en función de si misma. Dicho a sí a muchos os ha sonado a chino, ya que es un concepto muy abstracto, no es algo en lo que uno piense de forma natural, no es algo intuitivo. Citando la wikipedia la recursividad es

«…la forma en la cual se especifica un proceso basado en su propia definición.»

«Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.»

Simplificando al máximo la definición, a nivel de programación: la recursividad es una función que se llama a si misma. Cada vez que se llama a una función, se crea un juego de variables locales, de este modo, si la función hace una llamada a si misma, se guardan sus variables y parámetros, usando la pila, y la nueva instancia de la función trabajará con su propia copia de las variables locales. Cuando esta segunda instancia de la función retorna, recupera las variables y los parámetros de la pila y continua la ejecución en el punto en que había sido llamada.

Cuando estudié la recursividad en primero de DAI, los ejemplos que tuvimos que programar fueron dos: Una función que calcula un factorial y una función que calcula una sucesión de Fibonacci. Ambos son ejemplos clásicos.

Seguramente Taboada, mi profesor de Fundamentos de la programación me mataría por resolver así la función del factorial, porque siempre insistía en que «una función sólo puede tener una salida», pero después de tanto tiempo programando en VB.NET y en Java ya no me rompo la cabeza con eso y le pongo varias salidas aunque el ejemplo esté en C.

/*Función para un factorial, que recibe un entero*/

int factorial(int n) {
  if(n < 0) return 0; /*Si el número es negativo no se puede calcular el factorial*/
  else if(n > 1) return n*factorial(n-1); /* Recursividad, la función se llama a si misma */
  return 1; /* Si es igual a uno, devuelve uno y se termina la recursividad */
}

Podéis obviar la primera comprobación (la de si n<0) si en el main (o donde llaméis a la función por primera vez) ya comprobáis que no le estáis pasando un negativo (no se puede hacer el factorial de números negativos).

Sobre la sucesión de Fibonacci podéis informaros en ese link a la wikipedia, que es un coñazo explicarla. El programa que la calcula en C (y C++) sería el siguiente (esta vez pondré el programa completo y no sólo la función, porque da la casualidad que lo llevaba dentro del pendrive):

#include<stdio.h>

/*Programa que calcula una sucesión de Fibonacci*/
 void main(void)
 {
 int num=0;/*Entero que almace la cantidad de números a calcular*/
 int resultado=0;/*entero que almacena el resultado*/

printf("SERIE DE FIBONACCI\n");
 printf("Introduce la cantidad de numeros: ");
 scanf("%i",&num);
 printf("\t");

for(int i=0;i<=num-1;i++)
 {
   resultado = fibonacci(i);
   printf("%i ", resultado);
 }

printf("\n");
 }

/*****************************************************/
 /*Función que calcula la serie de Fibonacci*/
 int fibonacci(int n)
 {
 if (n<2)
  return n;
 else
  return fibonacci(n-1) + fibonacci(n-2);
 }

De nuevo pedir perdón por el sangrado, como en otras ocasiones, pero cuando hago copypaste desde Notepad++ o desde Notepad el wordpress no me mantiene la sangría (curiosamente desde GEDIT sí que lo mantiene, un minipunto para Linux). En todo caso, si copiáis y pegáis debería furrular.

En fin, y con esto os lego aquí este conocimiento que a mi me transmitió en su día el profesor José Taboada (aunque no estaría de acuerdo con la función del factorial, como dije antes). Espero que os sirva de utilidad.