Se dice que algo es recursivo si se define en función de sí mismo o a sí mismo. También se dice que nunca se debe incluir la misma palabra en la definición de ésta. El caso es que las definiciones recursivas aparecen con frecuencia en matemáticas, e incluso en la vida real. Un ejemplo: basta con apuntar una cámara al monitor que muestra la imagen que muestra esa cámara. El efecto es verdaderamente curioso, en especial cuando se mueve la cámara alrededor del monitor.

En matemáticas, tenemos múltiples definiciones recursivas:

- Números naturales:

  (1) 1 es número natural.
  (2) el siguiente número de un número natural es un número natural

- El factorial: n!, de un número natural (incluido el 0):

  (1) si n = 0 entonces: 0! = 1
  (2) si n > 0 entonces: n! = n · (n-1)!

Asimismo, puede definirse un programa en términos recursivos, como una serie de pasos básicos, o paso base (también conocido como condición de parada), y un paso recursivo, donde vuelve a llamarse al programa. En un computador, esta serie de pasos recursivos debe ser finita, terminando con un paso base. Es decir, a cada paso recursivo se reduce el número de pasos que hay que dar para terminar, llegando un momento en el que no se verifica la condición de paso a la recursividad. Ni el paso base ni el paso recursivo son necesariamente únicos.

Por otra parte, la recursividad también puede ser indirecta, si tenemos un procedimiento P que llama a otro Q y éste a su vez llama a P. También en estos casos debe haber una condición de parada.

Existen ciertas estructuras cuya definición es recursiva, tales como los árboles, y los algoritmos que utilizan árboles suelen ser en general recursivos.

Un ejemplo de programa recursivo en C, el factorial:

int factorial(int n)
{
  if (n == 0) return 1;
  return n * factorial(n-1);
}

Como se observa, en cada llamada recursiva se reduce el valor de n, llegando el caso en el que n es 0 y no efectúa más llamadas recursivas. Hay que apuntar que el factorial puede obtenerse con facilidad sin necesidad de emplear funciones recursivas, es más, el uso del programa anterior es muy ineficiente, pero es un ejemplo muy claro.

A continuación se expone un ejemplo de programa que utiliza recursión indirecta, y nos dice si un número es par o impar. Al igual que el programa anterior, hay otro método mucho más sencillo de determinar si un número es par o impar, basta con determinar el resto de la división entre dos. Por ejemplo: si hacemos par(2) devuelve 1 (cierto). Si hacemos impar(4) devuelve 0 (falso).

 /* declaracion de funciones, para evitar errores */

int par(int n);

int impar(int n);


int par(int n)
{
  if (n == 0) return 1;
  return impar(n-1);
}

int impar(int n)
{
  if (n == 0) return 0;
  return par(n-1);
}

En Pascal se hace así (notar el uso de forward):

function impar(n : Integer) : Boolean; forward;
function par(n : Integer) : Boolean; forward;


function par(n : Integer) : Boolean;
begin
  if n = 0 then par := true
  else par := impar(n-1)
end;


function impar(n : Integer) : Boolean;
begin
  if n = 0 then impar := false
  else impar := par(n-1)
end;

Ejemplo: si hacemos la llamada impar(3) hace las siguientes llamadas:
par(2)
impar(1)
par(0) -> devuelve 1 (cierto)

Por lo tanto 3 es un número impar.

¿Qué pasa si se hace una llamada recursiva que no termina?

Cada llamada recursiva almacena los parámetros que se pasaron al procedimiento, y otras variables necesarias para el correcto funcionamiento del programa. Por tanto si se produce una llamada recursiva infinita, esto es, que no termina nunca, llega un momento en el que no quedará memoria para almacenar más datos, y en ese momento se abortará la ejecución del programa. Para probar esto se puede intentar hacer esta llamada en el programa factorial definido anteriormente:

factorial(-1);

Por supuesto no hay que pasar parámetros a una función que estén fuera de su dominio, pues el factorial está definido solamente para números naturales, pero es un ejemplo claro.

¿Cuándo utilizar la recursión?

Para empezar, algunos lenguajes de programación no admiten el uso de recursividad, como por ejemplo el ensamblador o el FORTRAN. Es obvio que en ese caso se requerirá una solución no recursiva (iterativa). Tampoco se debe utilizar cuando la solución iterativa sea clara a simple vista. Sin embargo, en otros casos, obtener una solución iterativa es mucho más complicado que una solución recursiva, y es entonces cuando se puede plantear la duda de si merece la pena transformar la solución recursiva en otra iterativa. Posteriormente se explicará como eliminar la recursión, y se basa en almacenar en una pila los valores de las variables locales que haya para un procedimiento en cada llamada recursiva. Esto reduce la claridad del programa. Aún así, hay que considerar que el compilador transformará la solución recursiva en una iterativa, utilizando una pila, para cuando compile al código del computador.
Por otra parte, casi todos los algoritmos basados en los esquemas de vuelta atrás y divide y vencerás son recursivos, pues de alguna manera parece mucho más natural una solución recursiva.

Aunque parezca mentira, es en general mucho más sencillo escribir un programa recursivo que su equivalente iterativo. Si el lector no se lo cree, posiblemente se deba a que no domine todavía la recursividad. Se propondrán diversos ejemplos de programas recursivos de diversa complejidad para acostumbrarse a la recursión.

Ejercicio

La famosa sucesión de Fibonacci puede definirse en términos de recurrencia de la siguiente manera:

(1) Fib(1) = 1 ; Fib(0) = 0
(2) Fib(n) = Fib(n-1) + Fib(n-2) si n >= 2

¿Cuantas llamadas recursivas se producen para Fib(6)?. Codificar un programa que calcule Fib(n) de forma iterativa.
Nota: no utilizar estructuras de datos, puesto que no queremos almacenar los números de Fibonacci anteriores a n; sí se permiten variables auxiliares.

Ejemplos de programas recursivos

- Dados dos números a (número entero) y b (número natural mayor o igual que cero) determinar a^b.

int potencia(int a, int b)
{
  if (b == 0) return 1;
  else return a * potencia(a, b-1);
}

La condición de parada se cumple cuando el exponente es cero. Por ejemplo, la evaluación de potencia(-2, 3) es:
potencia(-2, 3) ->
(-2) · potencia(-2, 2) ->
(-2) · (-2) · potencia(-2, 1) ->
(-2) · (-2) · (-2) · potencia(-2, 0) ->
(-2) · (-2) · (-2) · 1

y a la vuelta de la recursión se tiene:

(-2) · (-2) · (-2) · 1 /=/ (-2) · (-2) · (-2) · potencia(-2,0)
< (-2) · (-2) · (-2) /=/ (-2) · (-2) · potencia(-2, 1)
< (-2) · 4 /=/ (-2) · potencia(-2,2)
< -8 /=/ potencia(-2,3)

en negrita se ha resaltado la parte de la expresión que se evalúa en cada llamada recursiva.

- Dado un array constituido de números enteros y que contiene N elementos siendo N >= 1, devolver la suma de todos los elementos.

int sumarray(int numeros[], int posicion, int N)
{
  if (posicion == N-1) return numeros[posicion];
  else return numeros[posicion] + sumarray(numeros, posicion+1, N);
}
...

int numeros[5] = {2,0,-1,1,3};
int N = 5;
printf("%d\n",sumarray(numeros, 0, N));

Notar que la condición de parada se cumple cuando se llega al final del array. Otra alternativa es recorrer el array desde el final hasta el principio (de derecha a izquierda):

int sumarray(int numeros[], int posicion)
{
  if (posicion == 0) return numeros[posicion];
  else return numeros[posicion] + sumarray(numeros, posicion-1);
}
...

int numeros[5] = {2,0,-1,1,3};
int N = 5;
printf("%d\n",sumarray(numeros, N-1));

- Dado un array constituido de números enteros, devolver la suma de todos los elementos. En este caso se desconoce el número de elementos. En cualquier caso se garantiza que el último elemento del array es -1, número que no aparecerá en ninguna otra posición.

int sumarray(int numeros[], int posicion)
{
  if (numeros[posicion] == -1) return 0;
  else return numeros[posicion] + sumarray(numeros, posicion+1);
}
...

int numeros[5] = {2,4,1,-3,-1};
printf("%d\n",sumarray(numeros, 0));

La razón por la que se incluye este ejemplo se debe a que en general no se conocerá el número de elementos de la estructura de datos sobre la que se trabaja. En ese caso se introduce un centinela -como la constante -1 de este ejemplo o la constante NULO para punteros, u otros valores como el mayor o menor entero que la máquina pueda representar- para indicar el fin de la estructura.

- Dado un array constituido de números enteros y que contiene N elementos siendo N >= 1, devolver el elemento mayor.

int mayor(int numeros[], int posicion)
{
  int aux;
  if (posicion == 0)
      return numeros[posicion];
  else {
    aux = mayor(numeros, posicion-1);
    if (numeros[posicion] > aux)
      return numeros[posicion];
    else
      return aux;
  }
}
...
int numeros[5] = {2,4,1,-3,-1};
int N = 5;
printf("%d\n", mayor(numeros, 4));

- Ahora uno un poco más complicado: dados dos arrays de números enteros A y B de longitud n y m respectivamente, siendo n >= m, determinar si B está contenido en A. Ejemplo:
A = {2,3,4,5,6,7,-3}
B = {7,-3} -> contenido; B = {5,7} -> no contenido; B = {3,2} -> no contenido

Para resolverlo, se parte del primer elemento de A y se compara a partir de ahí con todos los elementos de B hasta llegar al final de B o encontrar una diferencia.
A = {2,3,4,5}, B = {3,4}
--
2,3,4,5
3,4
^

En el caso de encontrar una diferencia se desplaza al segundo elemento de A y así sucesivamente hasta demostrar que B es igual a un subarray de A o que B tiene una longitud mayor que el subarray de A.
3,4,5
3,4

Visto de forma gráfica consiste en deslizar B a lo largo de A y comprobar que en alguna posición B se suporpone sobre A.
Se han escrito dos funciones para resolverlo, contenido y esSubarray. La primera devuelve cierto si el subarray A y el array B son iguales; tiene dos condiciones de parada: o que se haya recorrido B completo o que no coincidan dos elementos. La segunda función es la principal, y su cometido es ir 'deslizando' B a lo largo de A, y en cada paso recursivo llamar una vez a la función contenido; tiene dos condiciones de parada: que el array B sea mayor que el subarray A o que B esté contenido en un subarray A.

int contenido(int A[], int B[], int m, int pos, int desp)
{
  if (pos == m) return 1;
  else if (A[desp+pos] == B[pos])
    return contenido(A,B,m, pos+1, desp);
  else
    return 0;
}

int esSubarray(int A[], int B[], int n, int m, int desp)
{
  if (desp+m > n)
    return 0;
  else if (contenido(A, B, m, 0, desp))
    return 1;
  else
    return esSubarray(A, B, n, m, desp+1);
}
...
int A[4] = {2, 3, 4, 5};
int B[3] = {3, 4, 5};
if (esSubarray(A, B, 4, 5, 0)) printf("\nB esta contenido en A");
else printf("\nB no esta contenido en A");

Hay que observar que el requisito n >= m indicando en el enunciado es innecesario, si m > n entonces devolverá falso nada más entrar en la ejecución de esSubarray.

Este algoritmo permite hacer búsquedas de palabras en textos. Sin embargo existen algoritmos mejores como el de Knuth-Morris-Prat, el de Rabin-Karp o mediante autómatas finitos; estos algoritmos som más complicados pero mucho más efectivos.

- Dado un array constituido de números enteros y que contiene N elementos siendo N >= 1, devolver el elemento mayor. En este caso escribir un procedimiento, es decir, que el elemento mayor devuelto sea una variable que se pasa por referencia.

void mayor(int numeros[], int posicion, int *m)
{
  if (posicion == 0)
     *m = numeros[posicion];
  else {
    mayor(numeros, posicion-1, m);
    if (numeros[posicion] > *m)
      *m = numeros[posicion];
  }
}
...
int numeros[5] = {2,4,1,-3,-1};
int M;
mayor(numeros, 5-1, &M);
printf("%d\n", M);

Hay que tener cuidado con dos errores muy comunes: el primero es declarar la variable para que se pase por valor y no por referencia, con lo cual no se obtiene nada. El otro error consiste en llamar a la función pasando en lugar del parámetro por referencia una constante, por ejemplo: mayor(numeros, 5-1, 0); en este caso además se producirá un error de compilación.

- La función de Ackermann, siendo n y m números naturales, se define de la siguiente manera:

Ackermann(0, n) = n + 1
Ackermann(m, 0) = A(m-1, 1)
Ackermann(m, n) = A(m-1, A(m, n-1))

Aunque parezca mentira, siempre se llega al caso base y la función termina. Probar a ejecutar esta función con diversos valores de n y m... ¡que no sean muy grandes!. En Internet pueden encontrarse algunas cosas curiosas sobre esta función y sus aplicaciones.

Ejercicios propuestos

Nota: para resolver los ejercicios basta con hacer un único recorrido sobre el array. Tampoco debe utilizarse ningún array auxiliar, pero si se podrán utilizar variables de tipo entero o booleano.

- Dado un array constituido de números enteros y que contiene N elementos siendo N >= 1, escribir una función que devuelva la suma de todos los elementos mayores que el último elemento del array.

- Dado un array constituido de números enteros y que contiene N elementos siendo N >= 1, escribir una función que devuelva cierto si la suma de la primera mitad de los enteros del array es igual a la suma de la segunda mitad de los enteros del array.

- Dados dos arrays A y B de longitud n y m respectivamente, n >= m cuyos elementos estén ordenados y no se repiten, determinar si todos los elementos de B están contenidos en A. Recordar que los elementos están ordenados, de esta manera basta con realizar un único recorrido sobre cada array.

Conclusiones

En esta sección se ha pretendido mostrar que la recursividad es una herramienta potente para resolver múltiples problemas. Es más, todo programa iterativo puede realizarse empleando expresiones recursivas y viceversa.