PDF de programación - Capítulo 2: Recursividad

Capítulo 2: Recursividad.



2.1.- Introducción.


La recursividad consiste en realizar una definición de un
concepto en términos del propio concepto que se está definiendo.



Ejemplos:



•Los números naturales se pueden definir de la siguiente forma:
0 es un Número natural y el sucesor de un número natural
es también un número natural.



•El factorial de un número natural n, es 1 si dicho número es 0,
o n multiplicado por el factorial del número n-1, en caso
contrario.



•La n-ésima potencia de un número x, es 1 si n es igual a 0, o el
producto de x por la potencia (n-1)-ésima de x, cuando n es
mayor que 0.



En todos estos ejemplos se utiliza el concepto definido en la
propia definición.




Solución de problemas recursivos:


•División sucesiva del problema original en uno o varios más

pequeños, del mismo tipo que el inicial.


•Se van resolviendo estos problemas más sencillos.

•Con las soluciones de éstos se construyen las soluciones de los

problemas más complejos.



O lo que es lo mismo:



1.Un problema P se puede resolver conociendo la solución de
otro problema Q que es del mismo tipo que P, pero más
pequeño.

2.Igualmente, supongamos que pudiéramos resolver Q
mediante la búsqueda de la solución de otro nuevo
problema, R, que sigue siendo del mismo tipo que Q y P,
pero de un tamaño menor que ambos.

3.Si el problema R fuera tan simple que su solución es obvia o
directa, entonces, dado que sabemos la solución de R,
procederíamos a resolver Q y, una vez resuelto, finalmente
se obtendría la solución definitiva al primer problema, P.







3!= 3 * 2!

4! = 4 * 3!

2! = 2 * 1!


1! = 1 * 0!

Ejemplos simples de recursividad.

A) Cálculo del factorial de un número, por ejemplo, 5.

5! = 5 * 4!



DESCOMPOSICIÓN
DEL PROBLEMA



SOLUCIÓN CONOCIDA O DIRECTA



5! = 5 * 4! = 120



B) Búsqueda de una palabra en un diccionario.



4! = 4 * 3! = 24



3! = 3 * 2! = 6



1! = 1 * 0! = 1

2! = 2 * 1! = 2

0! = 1



RESOLUCIÓN DE
PROBLEMAS MÁS
COMPLEJOS A PARTIR
DE OTROS MÁS
SIMPLES




Características de los problemas que pueden ser
resueltos de manera recursiva:



4.Los problemas pueden ser redefinidos en términos de uno o
más subproblemas, idénticos en naturaleza al problema
original, pero de alguna forma menores en tamaño.



5.Uno o más subproblemas tienen solución directa o conocida,

no recursiva.

6.Aplicando la redefinición del problema en términos de
problemas más pequeños, dicho problema se reduce
sucesivamente a los subproblemas cuyas soluciones se
conocen directamente.

7.La solución a los problemas más simples se utiliza para

construir la solución al problema inicial.







Algoritmos recursivos:

diseño de la solución de un problema de manera recursiva



El algoritmo se llamará a sí mismo varias veces

¡Ojo al diseñar algoritmos recursivos!



pueden ser menos eficientes que que su solución iterativa



Algoritmo recursivo Implementación en un lenguaje de alto
nivel que permita recursividad (en nuestro caso, en Java).




2.2.- Diseño de módulos recursivos.


•Módulo M con una llamada a sí mismo: módulo recursivo

directo.


•Módulo M con una llamada a otro F, que hace una llamada a

M: Módulo recursivo indirecto.



Ejemplo: Implementación del factorial de un número.



public long factorial (long n)
{
if (n == 0) return 1;
else return n * factorial(n-1);
}



Dos partes principales:


8.La llamada recursiva, que expresa el problema original en

términos de otro más pequeño, y

9.el valor para el cual se conoce una solución no recursiva.
Esto es lo que se conoce como caso base: una instancia del
problema cuya solución no requiere de llamadas recursivas.



10.Actúa como condición de finalización de la función
recursiva. Sin el caso base la rutina recursiva se llamaría
indefinidamente y no finalizaría nunca.

11.Es el cimiento sobre el cual se construirá la solución



El caso base



completa al problema.



Ejemplo: Traza del factorial de 5.



Búsqueda de soluciones recursivas: cuatro preguntas
básicas.



•[P1] ¿Cómo se puede definir el problema en términos de uno o

más problemas más pequeños del mismo tipo que el original?



•[P2] ¿Qué instancias del problema harán de caso base?



•[P3] Conforme el problema se reduce de tamaño ¿se alcanzará

el caso base?



•[P4] ¿Cómo se usa la solución del caso base para construir una

solución correcta al problema original?



Ejemplo: la sucesión de Fibonacci.


1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...



•El tercer término de la sucesión se obtiene sumando el segundo
y el primero. El cuarto, a partir de la suma del tercero y el
segundo.


•El problema: calcular el valor del n-ésimo término de la

solución, que se obtendrá sumando los términos n-1 y n-2.



Las respuestas a la preguntas anteriores serían:


•[P1] fibonacci(n) = fibonacci(n-1) + fibonacci(n-2).


•[P2] Casos bases: fibonacci(1) = 1 y fibonacci(2)=1.


•[P3] En cada llamada a la rutina fibonacci se reduce el tamaño
del problema en uno o en dos, por lo que siempre se alcanzará
uno de los dos casos bases.



•[P4] fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1.
Se construye la solución del problema n==2 a partir de los dos
casos bases.






int fibonacci(int n)
{
if ((n == 1) || (n == 2)) return 1;
else return (fibonacci(n-2) + fibonacci(n-1));
}



Peculiaridades de esta función recursiva: más de un caso base y
más de una llamada recursiva (recursión no lineal).



Ejemplo: máximo común divisor de dos números m y n.


Ejemplo de problema en el que la solución al encontrar el caso
base es la propia solución del problema.

Algoritmo de Euclides:



Soluciones a las cuatro preguntas:


•[P1] Es evidente que MCD(m, n) ha sido definida en términos
de un problema del mismo tipo, pero justifiquemos que
MCD(m, n % m) es de tamaño menor que MCD(m, n):

entonces MCD(m, n)=n,
Si no, MCD(m, n) = MCD(n, m % n),



Si n divide a m,



n).

12.El rango de m % n es 0, ..., n-1, por tanto el resto es

siempre menor que n.


13.Si m > n, entonces MCD(n, m % n) es menor que MCD(m,


14.Si n > m, el resto de dividir m entre n es m, por lo que la
primera llamada recursiva es MCD(n, m mod n) es
equivalente a MCD(n, m), lo que tiene el efecto de
intercambiar los argumentos y producir el caso anterior.





•[P2] Si n divide a m, si y sólo si, m mod n = 0, en cuyo caso
MCD(m, n) = n, por tanto, se conseguirá el caso base cuando
el resto sea cero.



•[P3] Se alcanzará el caso base ya que n se hace más pequeño en

cada llamada y además se cumple que 0 * m mod n * n-1.



•[P4] En este caso, cuando se llega al caso base es cuando se
obtiene la solución final al problema, por lo que no se
construye la solución general en base a soluciones de
problemas más simples.



public int mcd (int m, int n)
{
if (m % n == 0) return n;
else return (mcd(n, m % n));
}



Ejemplo: conteo de ocurrencias de un valor en un vector.

Dado un vector de n enteros, el problema a resolver
recursivamente consiste en contar el número de veces que
un valor dado aparece en dicho vector.

Respuestas:

•[P1] Si el primer elemento = valor buscado, entonces la
solución será 1 más el número de veces que aparece
dicho valor en el resto del vector.



Si no, la solución al problema original será el número de
veces que el valor se encuentra en las posiciones
restantes



•[P2] El vector a está vacío =>ocurrencias en el vector= 0.


•[P3] Cada llamada recursiva se reduce en uno el tamaño
del vector, por lo que nos aseguramos que en N
llamadas habremos alcanzado el caso base.



•[P4] Cuando se encuentra una coincidencia se suma uno
al valor devuelto por otra llamada recursiva. El retorno
del control de las sucesivas llamadas comenzará
inicialmente sumando 0 cuando nos hayamos salido de
las dimensiones del vector.

Función en Java que implementa la solución recursiva:






Parámetros:


•el tamaño del vector (n),

•el propio vector (vector),

•el valor a buscar (objetivo) y

•el índice del primer elemento del vector a procesar

(primero).



public int contarOcurrencias (int n, int[] vector, int objetivo,
int primero)
{
if (primero > n-1) return 0;
else
{
if (vector[primero] == objetivo)


1));
else
primero+1));
}
}

return(1+contarOcurrencias(n,vector,objetivo,primero+

return(contarOcurrencias(n,vector,

objetivo,




Ejemplo: combinaciones sin repetición de n objetos
tomados de k en k.


Cuántas combinaciones de k elementos se pueden hacer
de entre un total de n (combinaciones sin repetición de n
elementos tomados de k en k).



Respuestas:


•[P1] El cálculo del número de combinaciones de n
elementos tomados de k en k se puede descompo