informe

Fundamentos de Programación II

Tema 2. Recursividad

Luís Rodríguez Baena (luis.rodriguez@upsam.net)
Universidad Pontificia de Salamanca (campus Madrid)
Escuela Superior de Ingeniería y Arquitectura

Naturaleza de la recursividad
Se dice que un objeto es
recursivo cuando forma parte de
si mismo.
● Permite definir un número infinito
de objetos mediante un enunciado
finito.

Enprogramació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.

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 O no tiene hijos es un árbol vacío.
Si O tiene 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 n es mayor que 0, n! = n (n-1)!

● Potencia de unnúmero.
x0 = 1
Si y > 0, xy = x xy-1

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.

Para evitar un bucle infinito, un
algoritmo recursivo tendrá:
● Caso trivial, caso baseo 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 recursivadevolver(Recursiva(…))
fin_si
…
fin_función
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(…))

● 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

5

Tipos de recursividad (II)
Según el modo en que se hace la llamada recursiva la recursividad
puede ser:
● De cabeza.
Lallamada 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
instrucciones se realizan antes de hacer la llamada.
o Las instrucciones se hacen en el mismo orden que lasllamadas.

● 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.

6

Tipos de recursividad (III)7

Llamadas a módulos recursivos
Llamadas anidadas (no recursivas).

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.

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...