4.1.2.3 Ejemplo de Aplicación 04

EJEMPLO DE APLICACIÓN

Ejemplo de uso: eliminación de recursividad

Suponga que una función F realiza un llamado recursivo dentro de su código, lo que se ilustra en la siguiente figura:

Si la llamada recursiva es lo último que hace la función F, entonces dicha llamada se puede substituir por un ciclo while. Este caso es conocido como tail recursion y en lo posible hay que evitarlo en la programación, ya que cada llamada recursiva ocupa espacio en la memoria del computador, y en el caso del tail recursion es muy simple eliminarla. Por ejemplo:

void imprimir(int[] a, int j) // versión recursiva

{

if (j<a.length)

{

System.out.println(a[j]);

imprimir(a, j+1); // tail recursion

}

}

void imprimir(int[] a, int j) // versión iterativa

{

while (j<a.length)

{

System.out.println(a[j]);

j=j+1;

}

}

En el caso general, cuando el llamado recursivo se realiza en medio de la función F, la recursión se puede eliminar utilizando una pila.

Por ejemplo: recorrido en preorden de un arbol binario.

// "raiz" es la referencia a la raiz del arbol

// llamado inicial: preorden(raiz)

// version recursiva

void preorden(Nodo nodo)

{

if (nodo!=null)

{

System.out.print(nodo.elemento);

preorden(nodo.izq);

preorden(nodo.der);

}

}

// primera version iterativa

void preorden(Nodo nodo)

{

Nodo aux;

Pila pila=new Pila(); // pila de nodos

pila.apilar(nodo);

while(!pila.estaVacia()) // mientras la pila no este vacia

{

aux=pila.desapilar();

if (aux!=null)

{

System.out.print(aux.elemento);

// primero se apila el nodo derecho y luego el izquierdo

// para mantener el orden correcto del recorrido

// al desapilar los nodos

pila.apilar(aux.der);

pila.apilar(aux.izq);

}

}

}

// segunda version iterativa

// dado que siempre el ultimo nodo apilado dentro del bloque if es

// aux.izq podemos asignarlo directamente a aux hasta que éste sea

// null, es decir, el bloque if se convierte en un bloque while

// y se cambia el segundo apilar por una asignacion de la referencia

void preorden(Nodo nodo)

{

Nodo aux;

Pila pila=new Pila(); // pila de nodos

pila.apilar(nodo);

while(!pila.estaVacia()) // mientras la pila no este vacia

{

aux=pila.desapilar();

while (aux!=null)

{

System.out.print(aux.elemento);

pila.apilar(aux.der);

aux=aux.izq;

}

}

}

Si bien los programas no recursivos son más eficientes que los recursivos, la eliminación de recursividad (excepto en el caso de tail recursion) le quita claridad al código del programa. Por lo tanto:

• A menudo es conveniente eliminar el tail recursion.
• Un método recursivo es menos eficiente que uno no recursivo, pero sólo en pocas oportunidades vale la pena eliminar la recursión.