662
Capítulo 15 Recursividad
y
D
al método. La llamada
C
se realiza primero, y su registro de activación se mete en la pila [parte (b) de la fi gura
15.9]. La llamada
B
al método todavía no ha terminado, y su registro de activación sigue en la pila de llamadas
a métodos. Cuando se ejecuta la llamada
C
, no realiza ninguna otra llamada al método, sino que simplemente
devuelve el valor
1
. Cuando este método regresa, su registro de activación se saca de la parte superior de la pila.
La llamada al método en la parte superior de la pila es ahora
B
, que continúa ejecutándose y realiza la llamada
D
al método. El registro de activación para la llamada
D
se mete en la pila [parte (c) de la fi gura 15.9]. La llamada
D
al método se completa sin realizar ninguna otra llamada, y devuelve el valor
0
. Después, se saca el registro de
activación para esta llamada de la pila. Ahora, ambas llamadas al método que se realizaron desde el interior de la
llamada
B
al método han regresado. La llamada
B
continúa ejecutándose, y devuelve el valor
1
. La llamada
B
al
método se completa y su registro de activación se saca de la pila. En este punto, el registro de activación para la
llamada
A
al método se encuentra en la parte superior de la pila, y el método continúa su ejecución. Este método
realiza la llamada
E
al método, cuyo registro de activación se mete ahora en la pila [parte (d) de la fi gura 15.9]. La
llamada
E
al método se completa y devuelve el valor
1
. El registro de activación para esta llamada al método se saca
de la pila, y una vez más la llamada
A
al método continúa su ejecución. En este punto, la llamada
A
no realizará
ninguna otra llamada al método y puede terminar su ejecución, para lo cual devuelve el valor
2
al método que
llamó a
A
(
fibonacci(3)=2
). El registro de activación de
A
se saca de la pila. Observe que el método en ejecución
es siempre el que tiene su registro de activación en la parte superior de la pila, y el registro de activación para ese
método contiene los valores de sus variables locales.
15.6 Comparación entre recursividad e iteración
En las secciones anteriores estudiamos los métodos
factorial
y
fibonacci
, que pueden implementarse fácil-
mente, ya sea en forma recursiva o iterativa. En esta sección compararemos los dos métodos, y veremos por qué
le convendría al programador elegir un método en vez del otro, en una situación específi ca.
Tanto la iteración como la recursividad se basan en una instrucción de control: la iteración utiliza una
instrucción de repetición (
for
,
while
o
do
…
while
), mientras que la recursividad utiliza una instrucción de
selección (
if
,
if
…
else
o
switch
). Tanto la iteración como la recursividad implican la repetición: la iteración
utiliza de manera explícita una instrucción de repetición, mientras que la recursividad logra la repetición a través
de llamadas repetidas al método. La iteración y la recursividad implican una prueba de terminación: la iteración
termina cuando falla la condición de continuación de ciclo, mientras que la recursividad termina cuando se llega
a un caso base. La iteración con repetición controlada por contador y la recursividad llegan en forma gradual a la
terminación: la iteración sigue modifi cando un contador, hasta que éste asume un valor que hace que falle la con-
dición de continuación de ciclo, mientras que la recursividad sigue produciendo versiones cada vez más pequeñas
del problema original, hasta que se llega a un caso base. Tanto la iteración como la recursividad pueden ocurrir
infi nitamente: un ciclo infi nito ocurre con la iteración si la prueba de continuación de ciclo nunca se vuelve falsa,
mientas que la recursividad infi nita ocurre si el paso recursivo no reduce el problema cada vez, de forma tal que
llegue a converger en el caso base, o si el caso base no se evalúa.
Para ilustrar las diferencias entre la iteración y la recursividad, examinaremos una solución iterativa para el
problema del factorial (fi guras 15.10 y 15.11). Observe que se utiliza una instrucción de repetición (líneas 12 y 13
de la fi gura 15.10), en vez de la instrucción de selección de la solución recursiva (líneas 9 a 12 de la fi gura 15.3).
Observe que ambas soluciones usan una prueba de terminación. En la solución recursiva, en la línea 9 se evalúa
el caso base. En la solución iterativa, en la línea 12 se evalúa la condición de continuación de ciclo; si la prueba
falla, el ciclo termina. Por último, observe que en vez de producir versiones cada vez más pequeñas del problema
original, la solución iterativa utiliza un contador que se modifi ca hasta que la condición de continuación de ciclo
se vuelve falsa.
1
// Fig. 15.10: CalculoFactorial.java
2
// Método factorial iterativo.
3
4
public class
CalculoFactorial
5
{
6
// declaración recursiva del método factorial
Figura 15.10
| Solución de factorial iterativa. (Parte 1 de 2).
15_MAQ_CAP_15_DEITEL.indd662
4/19/081:29:00AM