La Recursión

¿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.

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) · 1y 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,53,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,53,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 + 1Ackermann(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.