PDF de programación - Tema 3. Recursividad - Fundamentos de Programación II

Fundamentos de Programación II
Fundamentos de Programación II

Tema 3 Recursividad
Tema 3. Recursividad

Luis Rodríguez Baena ([email protected])

Universidad Pontificia de Salamanca
Escuela Superior de Ingeniería y Arquitectura

Naturaleza de la recursividad

 Se dice que un objetoes
 Se dice que un objeto es

recursivocuando forma parte de
si mismo.
● Permite definir un número infinito de
● Permite definir un número infinito de

objetos mediante un enunciado
finito.

 En programación
 En programación…

● La recursividad es la propiedad que
tienen los procedimientos y
funciones de llamarse a si mismos
para resolver un problema.

● Permite describir un número infinito
de operaciones de cálculo mediante
un programa recursivo finito sin
un programa recursivo finito sin
implementar de forma explícita
estructuras repetitivas.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

2

Naturaleza de la recursividad (II)

 Ejemplos de definiciones recursivas:

j
● Números naturales.

p

 0 es un número natural.
 El sucesor del número natural x(sucesor(x)) es también un

número natural
número natural.

● Estructuras de árbol.

 Si Ono tiene hijos es un árbol vacío.
 Si Otiene dos hijos t y t éstos también son árboles
 Si Otiene dos hijos,t1y t2, éstos también son árboles.

● Multiplicación.

x· 0 = 0
 Para y> 0 x·y=x+x·(y-1)
 Para y> 0, x y = x + x (y1)

● Factorial de un número.

 0! = 1
 Si nes mayor que 0, n!=n·(n-1)!
Si nes mayor que 0, n! n (n1)!

● Potencia de un número.

x0= 1
 Si y > 0, xy= x · xy-1

y

,

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

3

Partes de un algoritmo recursivo

 Un algoritmo recursivo genera la
 Un algoritmo recursivo genera la

repetición de una o más
instrucciones (como un bucle).
● Como cualquier bucle puede

p
crear un bucle infinito.

q

● Es necesario establecer una

condición de salida para terminar
la recursividad.
la recursividad.

 Para evitar un bucle infinito, un

algoritmo recursivo tendrá:
● Caso trivial, caso base o fin de

ió

recursión.
 La función devuelve un valor

simple sin utilizar la recursión (0!
= 1).

● Parte recursiva o caso general.
l

P t
 Se hacen llamadas recursivas que
se van aproximando al caso base.

i

entero : función Recursiva( )
entero : función Recursiva(…)
…
inicio

…
devolver(Recursiva( ))
devolver(Recursiva(…))
…

fin_función

entero : función Recursiva(…)
…
inicio

…
si … entonces

si no

_

//Caso base
devolver(…)
//Parte recursiva
devolver(Recursiva(…))

fin_si
…

fin_función

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

4

Tipos de recursividad

l

b

 Según el subprograma al que
S ú
se llama, existen dos tipos de
recursión:
● Recursividad simple o directa.

l

 La función incluye una referencia

explícita a si misma.
d
i ( ))
devolver(recursiva(…))
● Recursividad mutua o indirecta.

l

(

 El módulo llama a otros módulos de

forma anidada y en la última
forma anidada y en la última
llamada se llama al primero.

procedimiento Recursivo()
…
inicio
…
Recursivo(…)
…
fin_función

Recursividad directa

procedimiento Recursivo1()
…
inicio
…
Recursivo2(…)
…
fin función
_

procedimiento Recursivo2()
…
inicio
inicio
…
Recursivo1(…)
…
fin_función

Recursividad indirecta
Recursividad indirecta

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

5

Tipos de recursividad (II)

 Según el modo en que se hace la llamada recursiva la

g

q

recursividad puede ser:
● De cabeza.

● De cola.

● Intermedia.

● Múltiple.

● Anidada.
● Anidada.

 La llamada se hace al principio del subprograma, de forma que el resto de

instrucciones se realizan después de todas las llamadas recursivas
instrucciones se realizan después de todas las llamadas recursivas.

○ Las instrucciones se hacen en orden inverso a las llamadas.

 La llamada se hace al final del subprograma, de forma que el resto de

p g

q

,

instrucciones se realizan antes de hacer la llamada.

○ Las instrucciones se hacen en el mismo orden que las llamadas.

 Las instrucciones aparecen tanto antes como después de las llamadas
 Las instrucciones aparecen tanto antes como después de las llamadas.

 Se producen varias llamadas recursivas en distintos puntos del subprograma.

 La recursión se produce en un parámetro de la propia llamada recursiva.
 La llamada recursiva utiliza un parámetro que es resultado de una llamada

recursiva.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

6

Tipos de recursividad (III)

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

7

Llamadas a módulos recursivos

 Llamadas anidadas (no recursivas).
a adas a dadas ( o ecu s as)

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

8

Llamadas a módulos recursivos (II)

 El funcionamiento sería el mismo si se tratara de una única función que

se llamara a sí misma de forma recursiva
se llamara a sí misma de forma recursiva.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

9

Llamadas a módulos recursivos (III)

 El problema de sumar números entre 1 y n se puede definir en función de
 El problema de sumar números entre 1 y n se puede definir en función de
su tamaño (n), el problema se puede dividir en partes más pequeñas del
mismo problema y se conoce la solución del caso más simple (caso base,
suma(1) = 1). Por inducción se puede suponer que las llamadas más
pequeñas (por ejemplo Suma(n 1)) quedan resueltas
pequeñas (por ejemplo, Suma(n-1)) quedan resueltas.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

10

Llamadas a módulos recursivos (IV)

 En el caso del factorial…
 En el caso del factorial…

● Por definición, 0! = 1,
● Para cualquier número entero mayor que 0, n! = n * (n-1)!

 En este problema:

ó

● La solución de n! puede ser definida en función de su tamaño (n).
● Se puede dividir en instancias más pequeñas (<n) del mismo problema.
● Se conoce la solución de las instancias más simples (n=0).
● Por inducción, las llamadas más pequeñas (<n) pueden quedar resueltas.

ó

 Sabemos que 4! = 4 * 3!

 Conclusión: Se puede resolver por recursividad.

devuelve 24

4! = 4 * 3!

=

4 * 6

devuelve 6

3! = 3 * 2!

=

3 * 2

devuelve 2
devuelve 2

2! = 2 * 1!

=

2 * 1

devuelve 1

1! = 1 * 0!

=

1 * 1
1
devuelve 1
d

l

0! = 1 (caso base)

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

11

Llamadas a módulos recursivos (IV)

l

f

d

á l
Cada llamada a la función factorial devolverá el
C d ll
valor del factorial que se pasa como argumento.
entero función Factorial(valor entero : n)
inicio

ió f

l d

t

i

l

,

//Para cualquier n entero positivo <= 1, n! = 1
//n <= 1 sería el caso base, caso trivial o fin de la recursión
si n < 1 entonces
si_no

devolver(1)
//En caso contario n! = n * (n-1)!
//En cada llamada n se acerca al caso base
devolver(n * Factorial(n-1))

fin_si
_

fin función

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

12

Llamadas a módulos recursivos (V)

 La pila de llamadas a subrutinas.
 La pila de llamadas a subrutinas.

● Una estructura de tipo pilaes una estructura de datos en la que

la información se añade y se elimina por un extremo llamado
cima
cima.
 El último elemento que entra en la pila es el primero que sale.

● El registro de activación de procedimientoses un bloque de

memoria que contiene información sobre las constantes variables
memoria que contiene información sobre las constantes, variables
locales y parámetros que se pasan al procedimiento, junto con la
información de la dirección de retorno de esa llamada.

● Cada vez que se llama a un procedimiento (sea o no una llamada
● Cada vez que se llama a un procedimiento (sea o no una llamada
anidada, sea o no una llamada recursiva) se almacena el registro
de activación del procedimiento en la pila de llamadas a
subrutinas
subrutinas.
 Cuando el procedimiento termina, su registro de activación sale de la pila,
volviendo a la dirección de retorno que se ha almacenado y recuperando
el estado de las constantes, variables locales y parámetros.

y p

,

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

13

Llamadas a módulos recursivos (VI)

 En cada llamada a la función factorial
 En cada llamada a la función factorial

carga en la pila de llamadas su
registro de activación (cómo en
cualquier llamada a una subrutina).
● El último registro de activación que entra
● El último registro de activación que entra

es el primero que sale.

● Aunque los identificadores sean los

mismos no existe ambigüedad:

 Siempre se refieren al ámbito en el

que han sido declarados.

id d l

h

d

 Cuando se llega al caso base (n< 1),
el registro de activación se desapila y
el flujo de control del programa
regresa a la última llamada que se ha
regresa a la última llamada que se ha
hecho (cuando n=1), devolviendo
además el valor de retorno (1).

 Los registros de activación se van

desapilando restaurando los valores
desapilando, restaurando los valores
anteriores de n y devolviendo los
valores de retorno de cada una de
llamadas recursivas a la función (1, 1,
2, 6, 24).
,
)

,

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

14

Algoritmos recursivos

