660
Capítulo 15 Recursividad
de la llamada a
fibonacci( 1 )
, para producir el valor 2. Después, este valor fi nal se devuelve como el valor de
fibonacci( 3 )
.
La fi gura 15.7 genera ciertas preguntas interesantes, en cuanto al orden en el que los compiladores de Java
evalúan los operandos de los operadores. Este orden es distinto del orden en el que se aplican los operadores a
sus operandos; a saber, el orden que dictan las reglas de la precedencia de operadores. De la fi gura 15.7, parece
ser que mientras se evalúa
fibonacci( 3 )
, se harán dos llamadas recursivas:
fibonacci( 2 )
y
fibonacci( 1 )
.
Pero ¿en qué orden se harán estas llamadas? El lenguaje Java especifi ca que el orden de evaluación de los operan-
dos es de izquierda a derecha. Por ende, la llamada a
fibonacci( 2 )
se realiza primero, y después la llamada a
fibonacci( 1 )
.
Hay que tener cuidado con los programas recursivos como el que utilizamos aquí para generar números de
Fibonacci. Cada invocación del método
fibonacci
que no coincide con uno de los casos base (0 o 1) produce
dos llamadas recursivas más al método
fibonacci
. Por lo tanto, este conjunto de llamadas recursivas se sale rápi-
damente de control. Para calcular el valor 20 de Fibonacci con el programa de la fi gura 15.5, se requieren 21,891
llamadas al método
fibonacci
; ¡para calcular el valor 30 de Fibonacci se requieren 2,692,537 llamadas! A medida
que trate de calcular valores más grandes de Fibonacci, observará que cada número de Fibonacci consecutivo que
calcule con la aplicación requiere un aumento considerable en tiempo de cálculo y en el número de llamadas al
método
fibonacci
. Por ejemplo, el valor 31 de Fibonacci requiere 4,356,617 llamadas, y ¡el valor 32 de Fibonacci
requiere 7,049,155 llamadas! Como puede ver, el número de llamadas al método
fibonacci
se incrementa con
rapidez; 1,664,080 llamadas adicionales entre los valores 30 y 31 de Fibonacci, y ¡2,692,538 llamadas adicionales
entre los valores 31 y 32 de Fibonacci! La diferencia en el número de llamadas realizadas entre los valores 31 y
32 de Fibonacci es de más de 1.5 veces la diferencia en el número de llamadas para los valores entre 30 y 31 de
Fibonacci. Los problemas de esta naturaleza pueden humillar incluso hasta a las computadoras más poderosas del
mundo. [
Nota: en el campo de la teoría de la complejidad, los científi cos de computadoras estudian qué tanto
tienen que trabajar los algoritmos para completar sus tareas. Las cuestiones relacionadas con la complejidad se
discuten con detalle en un curso del plan de estudios de ciencias computacionales de nivel superior, al que gene-
ralmente se le llama “Algoritmos”. En el capítulo 16, Busqueda y ordenamiento, presentamos varias cuestiones
acerca de la complejidad]. En los ejercicios le pediremos que mejore el programa de Fibonacci de la fi gura 15.5,
de tal forma que calcule el monto aproximado de tiempo requerido para realizar el cálculo. Para este fi n, llamará
al método
static
de
System
llamado
currentTimeMillis
, el cual no recibe argumentos y devuelve el tiempo
actual de la computadora en milisegundos.
Tip de rendimiento 15.1
Evite los programas recursivos al estilo de Fibonacci, ya que producen una “explosión” exponencial de llamadas a
métodos.
Figura 15.7
| Conjunto de llamadas recursivas para
fibonacci ( 3 )
.
+
fibonacci( 3 )
fibonacci( 2 )
fibonacci( 1 )
return
+
fibonacci( 1 )
fibonacci( 0 )
return 1
return 0
return 1
return
15_MAQ_CAP_15_DEITEL.indd660
4/19/081:29:00AM