PDF de programación - Lección 11 - Recursividad

MIGUEL Á. TOLEDO MARTÍNEZ

CONTENIDO DE LA LECCIÓN 11



RECURSIVIDAD

Introducción


1.

2. Ejemplos de recursividad

2.1 Ejemplos 11.1, 11.2, 11.3, 11.4, 11.5, 11.6,


3. Funcionamiento interno de la recursividad

3.1 Ejemplos 11.7, 11.8, 11.9,


4. Soluciones no recursivas (iterativas)

4.1 Ejemplos 11.10, 11.11, 11.12


5. El problema de las Torres de Hanoi

5.1 Ejemplo 11.13


6. Uso de las pilas para simular recursividad

7. El problema de las ocho reinas

7.1 Ejemplo 11.14


8. Casos interesantes

8.1 Ejemplo 11.15: Información genealógica
8.2 Ejemplo 11.16: Árboles similares
8.3 Ejemplo 11.17: Árboles no similares


9. Retroceso

10. Programación no determinista

11. Retroceso cronológico

12. Retroceso de dependencia dirigida

13. Uso de la recursividad

13.1 Examen breve 30




14. Lo que necesita saber

15. Preguntas y problemas

15.1 Preguntas
15.2 Problemas

2

3
3

11
11

16
16

20
22

23

26
30

32
32
34
36

36

36

37

37

38
43

39

40
40
40















FUNCIONES – LECCIÓN 11

11-1

MIGUEL Á. TOLEDO MARTÍNEZ



LECCIÓN 11
RECURSIVIDAD


INTRODUCCIÓN


funciones puede darse de dos maneras diferentes:


Una función que se llama a sí mismo se dice que es recursiva. La recursividad en las

a. Directa. La función se llama directamente a sí misma. Por ejemplo, observe la figura 11.1,

funcionA() es una función y en alguna parte de ella aparece una llamada a sí misma:

funcionA()






Llamada a funcionA()

Figura 11.1. Recursividad directa

b. Indirecta. La función llama a otra función y esta a su vez llama a la primera. Por ejemplo, en la
figura 11.2a la función funcionA() llama a la función funcionB() y esta a su vez invoca a la primera;
es decir el control regresa a funcionA().































funcionA()

Llamada a funcionB()

funcionB()

Llamada a funcionA()











a)



funcionA()

Llamada a funcionB()

funcionB()

Llamada a funcionC()

funcionC()







Figura 11.2. Recursividad indirecta





b)


También se da la recursividad indirecta cuando una función llama a otra y ésta a una

tercera. Una vez ejecutada, el control regresa a la función que la llamó, lo mismo sucede en todos
los niveles. Por ejemplo, en la figura 11.2b la función funcionA() llama a la función funcionB(),
y esta llama a la función funcionC() Cuando funcionC() concluye, el control regresa a
funcionB(); y al terminar ésta, el control se transfiere a funcionA()




FUNCIONES – LECCIÓN 11

11-2

MIGUEL Á. TOLEDO MARTÍNEZ

En toda definición recursiva de un problema se debe establecer un estado básico (estado
primitivo, estado de salida o estado de terminación) Es decir, un estado en el cual la solución no
se presente de manera recursiva sino directamente. Además la entrada (datos) del problema
debe ir acercándose al estado básico.


Si dada la definición de un problema es posible determinar el estado básico y el
acercamiento paulatino al mismo, entonces se puede llegar a una solución. En otro caso se estaría
en presencia de una definición circular del problema.


Es importante comprender que cada instanciación (copia activa) de una función
recursiva es totalmente peculiar y tiene sus propios argumentos, variables locales, direcciones de
retorno, etc.


Objetivos de esta lección:

•••• Comprender y manejar el concepto de recursividad.
•••• Aprender como se escriben y utilizan funciones que se llaman a sí mismas.
•••• Resolver problemas utilizando recursividad.

Los ejemplos que aparecen a continuación, a pesar de que pueden resolverse de manera

no recursiva permiten ilustrar claramente el concepto de recursividad.



EJEMPLOS DE RECURSIVIDAD

Ejemplo 11.1



Solución


Escriba una función recursiva C++ para encontrar la suma de todos los enteros desde 1 hasta N.

Piense en esta operación por un minuto. ¿No es una operación recursiva clásica? Para encontrar la suma
de enteros de 1 a 5, ¿podría adicionar 5 a la suma de enteros de 1 a 4? Entonces, para encontrar la suma
de 1 a 4, adiciona 4 a la suma de enteros de 1 a 3, y así sucesivamente, ¿correcto? Expresada en símbolos:



sumaNumeros(5) = 5 + sumaNumeros(4)
sumaNumeros(4) = 4 + sumaNumeros(3)
sumaNumeros(3) = 3 + sumaNumeros(2)
sumaNumeros(2) = 2 + sumaNumeros(1)
sumaNumeros(1) = 1



Observe que sumaNumeros(1) es el estado básico, porque su valor es conocido. Ahora, traduciendo este
proceso a una función recursiva, se obtiene:

sumaNumero

ns
)(


1

n


+

sumaNumero

ns
(

−

)1

Si
Si

n
n

=
1

>

1





Esta expresión se puede expresar en seudocódigo como sigue:







FUNCIONES – LECCIÓN 11

11-3

MIGUEL Á. TOLEDO MARTÍNEZ

sumaNumeros(n)

si (n == 1) entonces
regresar (1).

si no



regresar ( n + sumaNumeros(n-1)).



La función C++ se codifica entonces directamente desde el algoritmo como:


/*************************************************************
Esta función recursiva calculará la suma de los enteros entre 1 hasta N
*************************************************************/
int sumaNumeros(int n)

{

if(n == 1)


else

return (1)

return (n + sumaNumeros(n – 1))

} // Fin de sumaNumeros()


Algoritmo 11.1. sumaNumeros



Ejemplo 11.2


El siguiente programa: SUMAENT.CPP, muestra el uso del algoritmo 11.1



int n;



//Para cin y cout

/* Tener en cuenta que el valor devuelto es de la clase int. Por lo tanto
la suma esta limitada a un máximo de 32767, en caso contrario se producirá
un sobreflujo.
*/

/* Este programa: SUMAENT.CPP, calcula la suma de los números enteros positivos comprendidos
entre 1 y el número dado.
*/

#include <iostream.h>

int sumaNumeros(int n);

void main(void)















}

int sumaNumeros(int n)







cout << "Dame un número entero mayor que cero: ";
cin >> n;

cout << "\nLa suma de los números enteros comprendidos entre 1 y " << n <<


" es: " << sumaNumeros(n) << endl;

if(n == 1)

else


return(n + sumaNumeros(n-1));

{










{




}

return(1);

FUNCIONES – LECCIÓN 11

11-4

MIGUEL Á. TOLEDO MARTÍNEZ

Ejemplo 11.3






















Factorial de un número: La notación n! se lee factorial de n e indica el producto de los enteros positivos
desde 1 hasta n. Por ejemplo:
















3! = 1 ×××× 2 ×××× 3
4! = 1 ×××× 2 ×××× 3 ×××× 4
5! = 1 ×××× 2 ×××× 3 ×××× 4 ×××× 5
n! = 1 ×××× 2 ×××× 3 ××××... ×××× (n-2) ×××× (n-1) ×××× (n)

También definimos 1! = 1 y 0! = 1. Si se le pide que desarrolle una función que calcule el factorial de un
número, ¿cómo le haría?

Si invertimos la definición de la fórmula tenemos:


n! = n (n-1) (n-2) ... 3 ×××× 2 ×××× 1

Por lo tanto, 4! = 4 ×××× 3 ×××× 2 ×××× 1. Observe que 3 ×××× 2 ×××× 1 es 3!; entonces, podemos definir 4! de manera
recursiva como:

En general, podemos definir n! como:

n! = n (n-1)!

(n-1)! = (n-1) (n-2)!









4! = 4 ×××× 3!

(n-2)! = (n-2) (n-3)!
.
.
.

Llegamos a definir entonces, el factorial de un número n en términos del factorial del número (n-1) de la
siguiente manera:

=

n
!


1

n


×

(

n

−

)!1

Si
Si

n
n

=
>

0
1

no

=

1



En la definición recursiva del factorial se da un estado básico (si n = 0 o n = 1, entonces el factorial vale
1), en el cual el problema ya no se define en términos de sí mismo sino que se asigna un valor directamente.
En el paso recursivo de la fórmula se utiliza el concepto de factorial aplicado a (n-1) Por ser un número
entero positivo será (n-1) un valor más cercano al estado básico (n = 0 o n = 1)

Una vez establecida la definición recursiva de los números factoriales, podemos comenzar a formular un
algoritmo recursivo. Considere el siguiente seudocódigo:

factorial(n)


INICIO





FIN.

x = n -1.

calcular x!.
regresar(n ×××× x!).

// (n-1)!


// n! = n × (n -1)!

La función factorial() estima el valor de n! calculando el valor de (n-1)! y luego multiplicando el resultado
por n. Sin embargo, como ya habrá notado, la segunda instrucción no está definida de modo correcto:
tenemos que encontrar una forma de calcular el valor de x!. Si lo piensa bien, verá que ya tenemos una:
factorial() Esta función calcula el factorial de un número. Apliquemos este conocimiento y volvamos a
escribir la rutina como:

FUNCIONES – LECCIÓN 11

11-5

MIGUEL Á. TOLEDO MARTÍNEZ

factorial(n)


INICIO





FIN.

x = factorial(n-1)
regresar(n ×××× x).

.
// (n-1)!
// n! = n × (n -1)!

Ahora bien, cuando calcule el valor de n!, la función se llamará a sí misma de modo recursivo para estimar
el valor de (n-1)!.

Cabe preguntarnos si la función está completa. Mirémosla con detenimiento y analicemos su ejecución
cuando calcula 2!. El procesamiento se inicia cuando se llama a la función con un argumento de 2.
Entonces ésta calcula 2! recursivamente llamándose a sí misma con un argumento de 1; para estimar 1!,
vuelve a llamarse a sí misma otra vez con un argumento de 0. La tercera copia (instancia) de la función se
llamará a sí misma con un argumento de –1, la siguiente con –2, y así sucesivamente. El problema está más
claro ahora: la función es recursiva hasta el infinito.

Todas las funciones recursivas necesitan una forma de detenerse, a la que hemos denominado estado básico
o primitivo. Se coloca, por lo común, en la parte superior de una función recursiva, y contiene instrucciones
que al final terminan la recursividad y comienzan a desapilar todas las llamadas anidadas. Si se le omite o
está incorrecta, com