4.4.6c Recursión
§1 Sinopsis
Se dice que una función es recursiva cuando se llama a sí misma. Es clásico el ejemplo de cálculo del factorial de un número mediante el uso de este tipo de funciones:
int factorial (int x) { return ( x > 1) ? x * factorial(x-1): 1; }
§2 Cada invocación sucesiva de estas
funciones crea un nuevo juego de todas las variables automáticas, con independencia de cuales sean sus valores en el
conjunto previo. En cambio existe una sola copia de las variables estáticas,
que es
compartida por todas las instancias de la función. Esta circunstancia debe ser
tenida en cuenta, cuando dichas variables sean utilizadas en funciones que puedan llamarse a sí mismas.
§3 La recursión ocupa espacio en la pila, porque se debe guardar una copia de cada juego de variables y tampoco
es muy rápida, pero tiene la ventaja de que resulta un código fácil de interpretar. Es especialmente adecuada para estructuras
que se definen recursivamente (algunos miembros de estas estructuras son punteros que referencian a objetos del mismo tipo
que la que se está definiendo), como árboles y listas enlazadas (las hemos denominado estructuras auto-referenciadas
4.5.8).
§4 Hay que prestar atención a que en algunos casos de funciones recursivas [1] es difícil de
manejar el valor devuelto. Como ejemplo tomemos la función búsqueda de un valor (key) en un árbol binario
( 4.5.8-3) que reproducimos aquí.
Esta función aparentemente devuelve un puntero al nodo buscado, o un nulo si fracasa la búsqueda.
struct base* busca(char key, struct base* ptr) { // buscar key
if (key == ptr->let) return ptr;
// Ok. encuentro!
if (key < ptr->let) {
if (ptr->izq == NULL) return NULL;
busca(key, ptr->izq);
}
if (key > ptr->let) {
if (ptr->der == NULL) return NULL;
busca(key, ptr->der);
}
return NULL;
}
El problema aquí, es que la función busca en el árbol de forma recursiva, pero es imposible saber "a priori"
cuantas invocaciones anidadas se producirán. Además, ninguna función aprovecha el valor devuelto por la anterior, por lo que
salvo la primera, cuyo retorno si puede ser utilizado por la función invocante, todos los demás valores de retorno se pierden
(una función puede devolver un valor, pero es potestad de la función invocante aprovecharlo o no
4.4.7).
En este contexto no
tiene sentido manejar directamente el valor devuelto por busca tal como se ha presentado. Por ejemplo, sería inútil el
siguiente trozo de código para saber si la búsqueda ha tenido éxito:
...
if (busca(key, ptr) != NULL){
...
}
La situación puede esquematizarse en la Fig.1. Cada nueva recursión recibe parámetros de la anterior, pero esta no
utiliza el valor devuelto.
La función usuaria (que hace la primera invocación a busca) siempre recibirá el resultado de la primera invocación, de modo que si el resultado se ha producido a partir de la segunda, el valor que recibe la función usuaria es irrelevante.
Para resolver el problema puede utilizarse una variable global que sea modificada por la instancia que realiza el
hallazgo, o un sistema más refinado. Por ejemplo el manejador de excepciones, que como se ha indicado
( 1.6), puede utilizarse como mecanismo
de return o break multinivel, y además pasar un valor desde el origen hasta el punto de captura.
En el primer caso, la función modificada podría tener el siguiente diseño:
void busca(char key, struct base* ptr) { // buscar key
if (key == ptr->let){gptr = ptr; return; } // Ok. encuentro!
if (key < ptr->let) {
if (ptr->izq == NULL) return;
busca(key, ptr->izq);
}
if (key > ptr->let) {
if (ptr->der == NULL) return;
busca(key, ptr->der);
}
return;
}
El cambio consiste en que la función devuelve siempre void, pero cuando se produce el encuentro modifica adecuadamente una constante global gptr (esta variable podría ser inicializada a NULL antes de la primera invocación a busca).
En el epígrafe dedicado a la búsqueda en un árbol
binario (
4.5.8-3), se exponen
sendos ejemplos concretos de lo anteriormente expuesto: una versión utilizando una variable global, y otra utilizando el
manejador de excepciones.
Otro ejemplo de función recursiva: obtener el equivalente hexadecimal de un valor expresado en decimal
( 9.5)
[1] Desde luego, no nos referimos a casos como el factorial, en el que precisamente la profundidad de la recursión es el factor determinante.