Recursión
MC Beatriz Beltrán Martínez
Primavera 2015
Primavera 2015
FCC - BUAP
• Una función recursiva es aquella que se llama a sí
misma.
• La recursividad es una alternativa a la repetición o
iteración.
• En tiempo de computadora y ocupación de memoria,
la solución recursiva es menos eficiente que la
iterativa, existen situaciones en las que la
recursividad es una solución simple y natural a un
problema que en otro caso será difícil de resolver
BBM
Introducción
102
Primavera 2015
FCC - BUAP
• La característica principal de la recursividad es que
siempre existe un medio de salir de la definición (caso
base o salida), y la segunda condición (llamado
recursivo) es propiamente donde se llama a sí misma.
• Una función recursiva simple en Java es:
public void infinito ()
{
infinito ();
}
BBM
Definición de un método recursivo
103
Primavera 2015
FCC - BUAP
• De manera más formal, una función recursiva es
invocada para solucionar un problema y dicha función
sabe cómo resolver los casos más sencillo (casos bases).
• Donde si la función es llamada desde un caso base, ésta
simplemente devuelve el resultado.
• Si es llamada mediante un problema más complejo, la
función lo divide en dos partes conceptuales: una parte
de dicha función sabe resolver y otra que no sabe
resolver.
BBM
Definición
104
Primavera 2015
FCC - BUAP
• Además esta segunda parte debe parecerse al problema
en sí; para tener la recursividad; pero debe ser más
simple.
• Debido a que se parece a la original la función lanza una
copia de ella misma, que se encargará del problema más
sencillo (llamado recursivo o paso de recursión).
• En esta parte se tendrá la devolución de un valor que era
desconocido inicialmente.
BBM
Definición
105
for (int i = k; i>=1; i--)
fact *= i;
Primavera 2015
FCC - BUAP
• El factorial de un entero no negativo n, esta definido
como:
n! = n * (n-1) * (n-2) * … *2 *1
• Donde 1! es igual a 1 y 0! se define como 1.
• El factorial de un entero k puede calcularse de manera
iterativa como sigue:
fact = 1;
BBM
Ejemplo con recursividad
106
1
n!  
 n * ( n  1)!
si n  0
si n  0
Donde el caso base es: 1
Si n = 0.
El caso general es: n * (n-1)!
Si n > 0.
• Por ejemplo si se quiere calcular el factorial de 5, se
tendría:
5! = 5*4*3*2*1
5! = 5*(4*3*2*1)
5! = 5*4!
Primavera 2015
FCC - BUAP
• Ahora de manera recursiva se puede definir el factorial
como:
BBM
Ejemplo con recursividad
107
5!
Se devuelve 5!=5*24=120
5* 4!
5* 4!
Se devuelve 4!=4*6=24
4* 3!
4* 3!
Primavera 2015
5!
FCC - BUAP
Valor devuelto 120
BBM
Ejemplo con recursividad
Se devuelve 3!=3*2=6
3* 2!
3* 2!
Se devuelve 2!=2*1=2
2* 1!
2* 1!
Se devuelve 1
1
1
108
• Caso general: Relaciona el resultado del algoritmo con
resultados de casos más simples. Dado que cada caso de
problema aparenta o se ve similar al problema original, la
función llama una copia nueva de si misma, para que
empiece a trabajar sobre el problema más pequeño y
esto se conoce como una llamada recursiva y también se
llama el paso de recursión.
Primavera 2015
FCC - BUAP
• Caso base: Es el caso más simple de una función
recursiva, y simplemente devuelve un resultado (el caso
base se puede considerar como una salida no recursiva).
BBM
Ejemplo con recursividad
109
Primavera 2015
FCC - BUAP
1. Obtener una definición exacta del problema a resolver.
(Esto, por supuesto, es el primer paso en la resolución
de cualquier problema de programación).
2. A continuación, determinar el tamaño del problema
completo que hay que resolver.
Este tamaño
determinará los valores de los parámetros en la
llamada inicial a la función.
3. Resolver el caso base en el que el problema puede
expresarse no recursivamente. Por último, resolver el
caso general correctamente en términos de un caso
más pequeño del mismo problema, una llamada
recursiva.
BBM
Método
110
Primavera 2015
FCC - BUAP
• Recursividad simple: Aquella en cuya definición sólo
aparece una llamada recursiva. Se puede transformar
con facilidad en algoritmos iterativos.
• Factorial
BBM
Tipos de recursión
• Recursividad múltiple: Se da cuando hay más de una
llamada a sí misma dentro del cuerpo de la función,
resultando más difícil de hacer de forma iterativa.
• Fibonacci
111
• Recursividad cruzada o indirecta: Son algoritmos donde
una función provoca una llamada a sí misma de forma
indirecta, a través de otras funciones. Es decir es aquella
en la que una función es llamada a otra función y esta a
su vez llama a la función que la llamó.
Primavera 2015
FCC - BUAP
• Recursividad anidada: En algunos de los argumentos de
la llamada recursiva hay una nueva llamada a sí misma.
• Ackerman
BBM
Tipos de recursión
112
int impar (int numi) {
if(numi==0)
return(0);
return( par(numi-1)); }
Primavera 2015
FCC - BUAP
Ejemplo: Par o Impar
int par(int nump) {
if (nump==0)
return(1);
return( impar(nump-1)); }
BBM
Tipos de recursión
113
Primavera 2015
FCC - BUAP
• Las principales cuestiones son la claridad y la eficiencia
de la solución.
• En general: Una solución no recursiva es más eficiente
en términos de tiempo y espacio de computadora.
• La solución recursiva puede requerir gastos
considerables, y deben guardarse copias de variables
locales y temporales.
• Aunque el gasto de una llamada a una función
recursiva no es peor, esta llamada original puede
ocultar muchas capas de llamadas recursivas internas.
• El sistema puede no tener suficiente espacio para
ejecutar una solución recursiva de algunos problemas.
BBM
Recursión vs. Iteración
114
Primavera 2015
FCC - BUAP
• Una solución recursiva particular puede tener una
ineficiencia inherente. Tal ineficiencia no es debida a
la elección de la implementación del algoritmo; más
bien, es un defecto del algoritmo en si mismo.
• Un problema inherente es que algunos valores son
calculados una y otra vez causando que la capacidad
de la computadora se exceda antes de obtener una
respuesta.
• La cuestión de la claridad en la solución es, no
obstante, un factor importante.
• En algunos casos una solución recursiva es más simple
y más natural de escribir.
BBM
Recursión vs. Iteración
115
Descargar

OBJETO