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

Fundamentos de Programación II

Tema 2. Recursividad

Luís Rodríguez Baena ([email protected])

Universidad Pontificia de Salamanca (campus Madrid)
Escuela Superior de Ingeniería y Arquitectura

Naturaleza de la recursividad

Se dice que un objeto es

recursivocuando forma parte de
si mismo.
● 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
implementar de forma explícita
estructuras repetitivas.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

2

Naturaleza de la recursividad (II)

Ejemplos de definiciones recursivas:

● Números naturales.

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

natural.

● Estructuras de árbol.

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

● Multiplicación.

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

● Factorial de un número.

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

● Potencia de un número.

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

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

3

Partes de un algoritmo recursivo

Un algoritmo recursivo genera la

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

crear un bucle infinito.

● Es necesario establecer una

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

Para evitar un bucle infinito, un

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

recursión.

La función devuelve un valor
simple sin utilizar la recursión
(0! = 1).

● Parte recursiva o caso general.
Se hacen llamadas recursivas

que se van aproximando al caso
base.

entero : función Recursiva(…)
…
inicio

…
devolver(Recursiva(…))
…

fin_función

entero : función Recursiva(…)
…
inicio

…
si … entonces

//Caso base
devolver(…)

si_no

//Parte recursiva
devolver(Recursiva(…))

fin_si
…

fin_función

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

4

Tipos de recursividad

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

La función incluye una referencia

explícita a si misma.

devolver(recursiva(…))
devolver(recursiva(…))

● Recursividad mutua o indirecta.

El módulo llama a otros módulos
de 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
…

Recursivo1(…)

…
fin_función

Recursividad indirecta

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

5

Tipos de recursividad (II)

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

puede ser:
● De cabeza.

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

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

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

● De cola.

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

instrucciones se realizan antes de hacer la llamada.

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

● Intermedia.

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

● Múltiple.

Se producen varias llamadas recursivas en distintos puntos del subprograma.

● Anidada.

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 (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

6

Tipos de recursividad (III)

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

7

Llamadas a módulos recursivos

Llamadas anidadas (no recursivas).

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

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.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

9

Llamadas a módulos recursivos (III)

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.

devuelve 10

Suma(4) = 4 + Suma(3)

=

4 + 6

devuelve 6

Suma(3) = 3 + Suma(2)

=

3 + 3

devuelve 3

Suma(2) = 2 + Suma(1)

=

2 + 1

devuelve 1

Suma(1) = 1 (caso base)

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

10

Llamadas a módulos recursivos (IV)

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.
Conclusión: Se puede resolver por recursividad.

devuelve 24

4! = 4 * 3!

=

4 * 6

devuelve 6

3! = 3 * 2!

=

3 * 2

devuelve 2

2! = 2 * 1!

=

2 * 1

devuelve 1

1! = 1 * 0!

=

1 * 1
devuelve 1

0! = 1 (caso base)

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

11

Llamadas a módulos recursivos (IV)

Cada llamada a la función factorial devolverá el valor del

factorial que se pasa como argumento.

entero función Factorial(valor entero : n)
inicio

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

devolver(1)

si_no

//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 (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

12

Llamadas a módulos recursivos (V)

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.

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
locales y parámetros que se pasan al procedimiento, junto con la
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

anidada, sea o no una llamada recursiva) se almacena el registro de
activación del procedimiento en la pila de llamadas a subrutinas.

Cuando el procedimiento termina, su registro de activación se desapila,

volviendo a la dirección de retorno que se ha almacenado y
recuperando el estado de las constantes, variables locales y
parámetros.

Universidad Pontificia de Salamanca (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

13

Llamadas a módulos recursivos (VI)

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 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.
han sido declarados.

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
hecho (cuando n=1), devolviendo
además el valor de retorno (1).

Los registros de activación se van

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 (Campus Madrid)

Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

14

Algoritmos recursivos

Cualquier algoritmo iterativo puede resolverse recursivamente.

● Una llamada recursiva, genera un bucle con una condición de salida

cuando se llega al caso base: se ejecuta la llamada hasta que se
cumple la condición de salida, como un bucle.

También, cualquier algoritmo recursivo puede r