Recursividad
Objetivos
- Presentar el concepto de recursividad.
- Conocer algunos ejemplos de procedimientos recursivos.
- Entender el paso del sistema iterativo al recursivo.
Introducción
El concepto de recursividad hace referencia a que un algoritmo se utilice a sí mismo para resolver un problema. El concepto en sí es muy sencillo y a la vez muy potente, ya que muchos problemas se pueden plantear de forma recursiva. Si un problema se puede arreglar con soluciones o versiones más pequeñas del mismo problema y estas versiones más pequeñas lo pueden reducir a casos triviales, podemos utilizar un algoritmo recursivo para resolverlo. Esta unidad solo quiere dar una noción básica del concepto de recursividad, por lo que las explicaciones se harán sobre ejemplos.
1. Ejemplo 1: números naturales
Los números naturales tienen su definición recursiva en matemáticas:
- Si
entonces 
El conjunto de números naturales es el mínimo conjunto que cumple estas dos propiedades.
Vemos que en este caso, para definir qué es un número natural, lo hacemos recursivamente, o sea, a partir de saber que n es recursivo, sabemos que n + 1 también lo es o, dicho de otra forma, si queremos saber si n es un número natural, tenemos que ver si este es 0, o si n-1 es natural. Entonces, si queremos saber si un número es natural o no, lo podríamos hacer con el siguiente algoritmo:
function isNatural(n: integer) : boolean
if n=0 then
return true;
end if
return isNatural(n-1);
end function
tBoolean isNatural(int n) {
if(n==0) {
return TRUE;
}
return isNatural(n-1);
}
En este código vemos un ejemplo de los dos elementos que todo algoritmo recursivo debe tener:
- Condición de finalización (en este caso cuando n es 0).
- Regla recursiva (una llamada recursiva con n-1).
Para entender lo que está pasando hay que tener en cuenta que, a pesar de ser la misma función, cada llamada a la función isNatural se añade al stack de memoria, con su zona de memoria independiente del resto. En la siguiente figura se simula lo que pasaría en la memoria cuando se llama isNatural(2) (se ha obviado el método principal):
Veremos que cuando se llama isNatural con el valor 2, este queda guardado en una zona de memoria. Siguiendo con el algoritmo, ya que n no es 0, se hace otra llamada a isNatural con el valor 1. Esta nueva llamada se añade a la pila y queda guardada en otra zona de memoria diferente. Como n todavía no es 0, se vuelve a hacer una llamada a isNatural con el valor 0 y esta nueva llamada también queda añadida a la pila utilizando otra zona de memoria. En este caso, como el parámetro tiene valor 0, se devolverá un true y se finalizará esta llamada. Cuando se finaliza la ejecución de una acción o función, toda la memoria ocupada por sus parámetros y variables se elimina y, por lo tanto, ahora solo quedarán las dos llamadas iniciales a la memoria. La segunda llamada devolverá el valor true que ha devuelto la última llamada y, por tanto, finalizará y quedará solo la primera llamada a la memoria. Finalmente esta llamada inicial retornará y también se eliminará de la memoria. Lo importante es ver que, aunque sea la misma función, a efectos prácticos es como si se tratara de funciones diferentes y, por tanto, los parámetros y variables que tenga son independientes entre llamadas.
2. Ejemplo 2: factorial
El factorial de un entero positivo n (escrito n!) Se define como el producto de todos los números enteros positivos desde 1 hasta n. Es decir:
n! = 1 x 2 x 3 x ... x (n-1) x n
Una posible implementación de la función factorial utilizando estructuras iterativas podría ser:
function fact(n: integer) : integer
var
i : integer
f : integer
end var
f:=1;
for i:=1 to n do
f:=f*i;
end for
return f
end function
unsigned int i=0;
unsigned int f=1;
for(i=1; i<=n ; i++) {
f*=i;
}
return f;
}
Si lo piensamos de forma recursiva, podemos ver que factorial(n) es lo mismo que n x factorial(n-1). Por lo tanto, podríamos escribirlo como:
function fact(n: integer) : integer
if n==1 then
return 1;
end if
return n*fact(n-1);
end function
if(n==1) {
return 1;
}
return n*fact(n-1);
}
A continuación se muestra un esquema de lo que pasaría en la pila de programas (program stack) si hiciéramos una llamada a este método para n = 3 dentro del programa principal main. De izquierda a derecha se muestra la evolución temporal, que corresponde a los siguientes pasos:
- En la pila solo está el main.
- Cuando desde el main se llama fact(3), en la pila se hace un push de la información referente a la función fact. En este caso, el parámetro n tiene un valor de 3, que es lo que se le ha indicado en la llamada.
- Como n no tiene un valor igual a 1 se devuelve el resultado de la expresión n * fact(n-1)*. Como el valor de n es 3, es necesario evaluar la expresión 3 * fact(2), y por tanto, se hace una llamada a la función fact pasando como parámetro el 2.
- Al hacer la llamada a fact(2), en la pila se hace un push de la información referente a la función fact, donde, en este caso, el parámetro n tiene un valor de 2.
- Como n no tiene un valor igual a 1 se devuelve el resultado de la expresión n * fact(n-1). Como el valor de n es 2, hay que evaluar la expresión 2 * fact(1), y por tanto, hay que hacer una llamada a la función fact pasando como parámetro el 1.
- Como ahora n tiene un valor igual a 1, entra en el if y devuelve el valor 1. En el retorno se hace un pop de la pila, que elimina toda la información de la última función que se había añadido.
- Dado que ahora ya tenemos el valor de fact(1), se puede evaluar la expresión 2 * fact(1), y se devuelve el valor 2. Cuando hacemos el retorno, se hace un pop de la pila, eliminando toda la información de la última función que se había añadido.
- Dado que ahora ya tenemos el valor de fact(2), se puede evaluar la expresión 3 * fact(3) y se devuelve el valor 6. En el retorno, se hace un pop de la pila, que elimina toda la información de la última función que se había añadido, y solo deja en la pila la información de la función main, que se eliminará cuando esta finalice.
3. Ejemplo 3: tratamiento secuencial
En general, la mayoría de los algoritmos que tratan secuencias son susceptibles de ser formulados de forma recursiva. Vamos a ver un ejemplo simple: mostrar todos los elementos de un vector de enteros. Suponed que tenemos un vector de valores enteros, finalizado por un valor -1 que marca el final de la secuencia. Si lo planteáramos como un algoritmo iterativo, tendríamos:
action writeVector(v: vector of integer)
var
i : integer
end var
i:=1
while v[i]<>-1 do
writeInteger(v[i]);
i:=i+1;
end while
end action
int i=0;
while(v[i]!=-1) {
printf("%d", v[i]);
i++;
}
}
Un planteamiento recursivo sería mostrar el primer elemento de la secuencia y luego volver a llamar al método recursivo para mostrar el resto de los elementos. Vamos procesando cada elemento de la secuencia (en este caso simplemente mostrar) hasta llegar al elemento que nos marca el final de la secuencia. Para convertirlo en recursivo, hay que buscar la repetición de un patrón, por ejemplo, imaginemos que tenemos el siguiente vector:
{1, 2, 3, 4, -1}
La llamada
writeVector({1, 2, 3, 4, -1})
es equivalente a mostrar el primer elemento y llamar:
writeVector({2, 3, 4, -1})
Por lo tanto, vemos que podemos dividir el problema en otro más simple (es una parte del problema inicial). Además tenemos un caso trivial, que es writeVector({-1}) en el que no hay que hacer nada, ya que tenemos un vector sin ningún elemento para mostrar. Por lo tanto, podemos definir una versión recursiva de la función writeVector.
Vamos a ver dos versiones para implementar este algoritmo, una con el uso de funciones auxiliares y la otra con punteros.
3.1. Funciones auxiliares
En algunos casos, el planteamiento recursivo requiere introducir información adicional para poder controlar la recursividad. Para añadir esta información será necesario crear una nueva función o acción con parámetros adicionales. En este caso, incorporaremos el índice de la primera posición de la secuencia que hay que procesar. Para ello, vamos a crear una nueva acción writeVector_aux que, además del vector, tendrá la primera posición a procesar. La acción writeVector asignará los valores iniciales para el proceso recursivo:
action writeVector_aux(v: vector of integer; i : integer)
if v[i]<>-1 then
writeInteger(v[i]);
writeVector_aux(v, i+1);
end if
end action
action writeVector(v: vector of integer)
writeVector_aux(v, 1);
end action
if(v[i]!=-1){
printf("%d", v[i]);
writeVector_aux(v, i+1);
}
}
void writeVector(int *v) {
writeVector_aux(v, 0);
}
3.2. Punteros
Otra posibilidad para implementar este algoritmo es el uso de punteros. En el caso concreto de C, podemos aprovechar el hecho de que un vector realmente es un puntero a la primera posición del vector y, por tanto, no necesitamos ningún método auxiliar:
if(*v!=-1) {
printf("%d", *p);
writeVector(p+1);
}
}
En este caso, lo que hacemos es mostrar el contenido del puntero (que es lo mismo que v[0]) y desplazar el puntero una posición antes de volver a hacer la llamada recursiva.
Resumen
En esta unidad hemos conocido el concepto de programación recursiva en contraste con la programación iterativa y hemos visto algunos ejemplos sencillos de su aplicación.