658
Capítulo 15 Recursividad
15.4 Ejemplo de uso de recursividad: serie de Fibonacci
La
serie de Fibonacci
,
0, 1, 1, 2, 3, 5, 8, 13, 21, …
empieza con 0 y 1, y tiene la propiedad de que cada número subsiguiente de Fibonacci es la suma de los dos
números Fibonacci anteriores. Esta serie ocurre en la naturaleza y describe una forma de espiral. La proporción
de números de Fibonacci sucesivos converge en un valor constante de 1.618…, un número denominado
propor-
ción dorada
, o
media dorada
. Los humanos tienden a descubrir que la media dorada es estéticamente placentera.
A menudo, los arquitectos diseñan ventanas, cuartos y edifi cios con una proporción de longitud-anchura en la
que se utiliza la media dorada.
La serie de Fibonacci se puede defi nir de manera recursiva como:
fi bonacci(0) = 0
fi bonacci(1) = 1
fi bonacci(
n) = fi bonacci(n – 1) + fi bonacci(n – 2)
Observe que hay dos casos base para el cálculo de Fibonacci:
fibonacci(0)
se defi ne como 0, y
fibonacci(1)
se
defi ne como 1. El programa de la fi gura 15.5 calcula el
i-ésimo número de Fibonacci en forma recursiva, usando el
método
fibonacci
(líneas 7 a 13). El método
mostrarFibonacci
(líneas 15 a 20) prueba a
fibonacci
, mostrando
los valores de Fibonacci del 0 al 10. La variable
contador
creada en el encabezado de la instrucción
for
en la
línea 17 indica cuál número de Fibonacci se debe calcular para cada iteración del número
for
. Los números de
Fibonacci tienden a aumentar con rapidez. Por lo tanto, utilizamos
long
como el tipo del parámetro y el tipo
de valor de retorno del método
fibonacci
. En la línea 9 de la fi gura 15.6 se hace una llamada al método
mostrar-
Fibonacci
(línea 9) para calcular los valores de Fibonacci.
5
{
6
// calcula los factoriales del 0 al 10
7
public static void
main( String args[] )
8
{
9
CalculoFactorial calculoFactorial =
new
CalculoFactorial();
10
calculoFactorial.mostrarFactoriales();
11
}
// fin del método main
12
}
// fin de la clase PruebaFactorial
Figura 15.4
| Prueba del método
factorial
. (Parte 2 de 2).
1
// Fig. 15.5: CalculoFibonacci.java
2
// Método fibonacci recursivo.
3
4
public
class
CalculoFibonacci
5
{
Figura 15.5
| Números de
Fibonacci
generados con un método recursivo. (Parte 1 de 2).
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
15_MAQ_CAP_15_DEITEL.indd658
4/19/081:28:59AM