Disponible la nueva versión "donationware" 7.3 de OrganiZATOR
Descubre un nuevo concepto en el manejo de la información.
La mejor ayuda para sobrevivir en la moderna jungla de datos la tienes aquí.

Curso C++

[Home]  [Inicio]  [Índice]


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)

  Inicio.


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