Recursion

Recursion - Lenguaje C++

1. Programación II
Mauricio Paletta
Coordinación General de Pregrado
UNIVERSIDAD NACIONAL EXPERIMENTAL DE GUAYANA
INGENIERÍA EN INFORMÁTICA
Programación II
Recursión
Presentación

2. Programación II
Definición
Recursión es el fenómeno mediante el cual
algo (proceso / estructura) se puede definir
en términos de sí mismo.
Un procesoes recursivo cuando en el
cuerpo de su definiciónse encuentra una
llamada al mismo proceso.
Una estructuraes recursiva cuando la
misma estructura es parte de su definición.

3. Programación II
Definición
NOTA: La clave para entender recursión es
saber diferenciar / identificar lo que se está
definiendo (el problema) de la definición.
Luego, colocar en la definición lo que se
está definiendo permite dar una definición
recursiva del problema.

4. Programación II
Proceso recursivo
En términos algorítmicos, un proceso
recursivo es una función / procedimiento que
tiene una llamada a la misma función /
procedimiento en su bloque de instrucciones.
NOTA: La mejor manera de codificar un
proceso recursivo es obtener primero la
definición recursiva del problema.

5. Programación II
Proceso recursivo
NOTA: Todos los problemas tienen tanto una
definición recursiva como una no recursiva.
A veces no es trivial encontrar una a partir
de la otra.
Algunos problemas son más fáciles de
codificar de forma recursiva. Entender /
usar recursión es muy importante en estos
casos.

6. Programación II
Proceso recursivo
Si un proceso recursivo se llama a sí mismo
tiene que pararen algún momento (caso
contrario hay un proceso “infinito” de
acumulaciones de llamadas, hasta que los
recursos computacionales lo permitan).
Quiere decir que es necesario identificar una
condición de parada de la recursión.

7. Programación II
Proceso recursivo
En resumen, para codificar un proceso de
manera recursiva se requiere dos cosas:
1)Tener la definición recursiva del
problema.
2)Identificar la condición de parada (por lo
general es lo primero que se hace).

8. Programación II
Proceso recursivo
Ejemplo: Factorial de un número.
Definición no recursiva:
Fac(N) = N x (N-1) x (N-2) x … x 1
Lo que se
está
definiendo
La
definición

9. Programación II
Proceso recursivo
Ejemplo: Factorial de un número.
Definición no recursiva:
Fac(N) = N x (N-1) x (N-2) x … x 1
Lo que se
está
definiendo
La
definición

10. Programación II
Proceso recursivo
Ejemplo: Factorial de un número.
Definición no recursiva:
Fac(N) = N x (N-1) x (N-2) x … x 1
Lo que se
está
definiendo
La
definición

11. Programación II
Proceso recursivo
Fac(5) = 5 x 4 x 3 x 2 x 1
Nótese que:
Fac(4) = 4 x (3) x (2) x 1
Entonces:
Fac(5) = 5 x Fac(4)

12. Programación II
Proceso recursivo
Definición recursiva:
Fac(N) = N x Fac(N-1)
Lo que se
está
definiendo
Lo que se está definiendo
está dentro de la definición
Fac(1) = Fac(0) = 1
Condición
de parada

13. Programación II
Proceso recursivo

14. Programación II
Proceso recursivo
Ejemplo: Término de Fibonacci.
Definición no recursiva:
Fib(N) = 0, 1, 1, 2, 3, 5, 8, 13, …
Lo que se
está
definiendo
La
definición

15. Programación II
Proceso recursivo
Fib(8) = 13
Nótese que:
13 = 5 + 8= Fib(6) + Fib(7)
Entonces:
Fib(8) = Fib(6) + Fib(7)

16. Programación II
Proceso recursivo
Definición recursiva:
Fib(N) = Fib(N-2) + Fib(N-1)
Lo que se
está
definiendo
Lo que se está definiendo
está dentro de la definición
Fib(1) = 0
Fib(2) = 1
Condición
de parada

17. Programación II
Proceso recursivo

18. Programación II
Proceso recursivo
Ejemplo: Torres de Hanoipara N discos.
1)Un disco no
puede colocarse
sobre otro disco
de tamaño
menor.
2)Sólo puede
moverse un
disco a la vez.

19. Programación II
Proceso recursivo
Lo que se está definiendo: mover N discos
de un poste a otro.
Problema: mover N discos del poste 1 al
poste 3.
Definición recursiva: mover N-1 discos del
poste 1 al poste 2; mover disco N del poste
1 al poste 3; mover N-1 discos del poste 2
al poste 3.

20. Programación II
Proceso recursivo
Este es del tipo de problema muy difícil de
resolver utilizando una estrategia diferente
a la recursión.
Utilizando la recursión el problema se
resuelve muy simple, basta seguir la
lectura de la definición.
Nótese la complejidad del problema
cuando N crece.

21. Programación II
Proceso recursivo

22. Programación II
Proceso recursivo

23. Programación II
Proceso recursivo

24. Programación II
Estructura recursiva
Ocurre cuando uno de los campos o atributos
de la estructura (por ejemplo una clase)
coincide con el mismo tipo de la estructura
que se está definiendo.
También puede darse con direcciones de
memoria o apuntadores para definir
estructuras de datos no lineales (es lo más
común).

25. Programación II
Estructura recursivaAlgoRecursivo