Programación IIRecursividad
Igor Santos Grueiro
“Para entender la
recursividad, primero hay que entender lo qué
es la recursividad”
-Un programador anónimo
?Hello world
¡¿QUÉ?!
La recursividad consiste en definir una entidad en función de sí misma
Podemos definir recursivamente
Tipos de datos Problemas
Definamos un tipo de datos de manera recursiva: clase Nodo
Object elementoNodo siguiente
Ejemplo de recursividad de tipos: Nodo
public class Nodo{private Object elemento;
private Nodosiguiente;
// Seguiría la definición …}
Ahora, a por la difícil: recursividad de ejecución o recursividad de problema
La recursividad de ejecución es la posibilidad de definir un problema en función del propio problema
Dicho de otro modo: una función que dentro
de su código se llama …
¡A SÍ MISMA!
Si se llama directamente a sí misma:recursividad directa
Si llama a otra a función que vuelve a llamar a la función original (1-n veces):
recursividad indirecta o mutua
Recursividad directa
public static int funcionRec(int n){if (n == 0){
return 1;}else{
return n * funcionRec(n-1);}
}
Se llama a sí misma directamente
Recursividad indirecta o mutua
public static boolean impar (int numero){ if (numero==0) return false; else return par(numero-1); }
public static boolean par (int numero){ if (numero==0) return true; else return impar(numero-1); }
Se llaman entre ellas
Para que una función pueda ser recursiva tienen que cumplirse
ciertos requisitos:
Que pueda definirse en términos de sí misma
Que exista un criterio de finalización o “caso base”
public static int funcionRec(int n){if (n == 0){
return 1;}else{
return n * funcionRec(n-1);}
}
Es el caso base
Que en cada llamada recursiva se esté más cerca de cumplirse
el Caso Base
public static int funcionRec(int n){if (n == 0){
return 1;}else{
return n * funcionRec(n-1);}
}
Al ir restando 1, nos acercamos al caso base: el número es 0
Que se resuelva el problema en un tiempo limitado o finito
Un ejemplo mítico: el
cálculo del factorial de un número
x!
Lo definimos matemáticamente
Solución iterativa:
x! = 1 · 2 · … · (x -1) · x
Solución recursiva:
Si x = 0 x! = 1Si x > 0 x! = x · (x-1)!
public static int factorial(int n){int fact = 1;for (int i = 1 ; i <= n ; i++){
fact *= i;}return fact;
}
Solución iterativa en Java
Haced la solución recursiva del procedimiento de cálculo del
factorial de un número
1 Definimos el caso base
public static int factorial(int n){if (n == 0){
return 1;}
}
El factorial de 0 es 1
2 Llamamos a la función
acercándonos al caso base
public static int factorial(int n){if (n == 0){
return 1;}else{
return n * factorial(n-1);}
}
Ejemplo n= 3
public static int factorial(int n){
if (n == 0){return 1;
}else{
return n * factorial(n-1);
}}
n
Valor de retorno 3 *
32
2 *
1
1 *
0
16
¡Hecho!
Ejercicio 1
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Diseñad un método que calcule la potencia de un numero real elevado a
un entero (en función de multiplicaciones sucesivas).
Tanto solución iterativa como recursiva
public static double potencia(double base, int exp){double pot = 1;for (int i=1; i<= exp; i++){ pot = pot * base;}return pot;
}
Solución iterativa
public static double potencia(double base, int exp){if (exp == 0) return 1;else return (base * potencia(base, exp - 1));
}
Solución recursiva
Ejercicio 2
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribid un método que calcule la suma de los N (N>0) primeros números naturales.
Solución recursiva
public static int sumaNaturales(int n) {// Caso base: la suma de los números hasta 0 es 0if (n == 0)
return 0;else
return (n + sumaNaturales(n - 1));}
Solución recursiva primera versión
public static int sumaNaturales(int n) {// Caso base: la suma de los números hasta 1 es 1if (n == 1)
return 1;else
return (n + sumaNaturales(n - 1));}
Solución recursiva segunda versión
Ejercicio 3
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribid un método que visualice los N primeros números naturales del 1 al N
Solución recursiva
public static void visualizarNumerosHastaN(int n) {if (n > 0) {
visualizarNumerosHastaN(n - 1);System.out.println(n);
}// Caso base: Si hemos llegado a 0 no muestro // nada
}
Solución recursiva
Ejercicio 4
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribir un método que visualice los N primeros números naturales del N al 1
Solución recursiva
public static void visualizarNumerosDesdeN(int n) {if (n > 0) {
System.out.println(n);// Se hace después la llamada para ir de // N a 1visualizarNumerosDesdeN(n - 1);
}// Caso base: Si hemos llegado a 0 no muestro // nada
}
Solución recursiva
Ejercicio 5
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribid un método que visualice los dígitos de un número natural N al revés
N = 7815 visualizar el numero 5187
public static void visualizarDigitosReves(int n) {// El caso base es que hemos llegado // al último digito (<10)
if (n < 10) {System.out.println(n);
} else {System.out.print(n % 10);visualizarDigitosReves(n / 10);
}}
Solución recursiva
Ejercicio 6
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribid un método que visualice los dígitos de un número natural N, uno por línea.
public static void visualizarDigitos(int n) {// El caso base es que hemos llegado // al último digito (<10)if (n < 10){
System.out.println(n);}else {
int digito = n % 10;visualizarDigitos(n / 10);System.out.println(digito);
}}
Solución recursiva
Ejercicio 7
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribid un método que sirva para subrayar un texto
public static void subrayar(int longitud){if (longitud > 0) {
System.out.print("_");subrayar(longitud-1);
}// El caso base es que la longitud sea 0
}
Solución recursiva
Búsqueda binaria
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribid un método que busque un valor en un array de enteros de un modo dicotómico (el array está ordenado de menor a mayor).
Búsqueda dicotómica o binaria
1 3 5 8 9
Valor a buscar 3
Valor medio
Si el valor medio es mayor que el valor a buscar …
1 3
Valor medioComo el valor medio es igual que el valor a buscar
Devolvemos la posición del valor medio: 1
public static int busquedaBinaria(int [] aEnteros, int valor, int rangoMenor, int rangoMayor){
int med = (rangoMayor - rangoMenor)/2 + RangoMenor;
if (rangoMenor > rangoMayor){return -1;
}else if (aEnteros[med] < valor){
return busquedaBinaria(aEnteros, valor, med + 1,rangoMayor);
}else if (aEnteros[med] > valor){
return busquedaBinaria(aEnteros, valor, rangoMenor, med - 1);
}else{
return med;}
}
Solución recursiva
Un ejemplo
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Escribir un método que sume los elementos de un array de manera recursiva
public static void main(String[] args){int [] aNumeros = {1, 3, 5, 7, 9, 11, 13};int suma =sumarArray(aNumeros);
System.out.println(suma);}
public static int sumarArray(int [] a) {
}
Partimos de esto
A veces se llama un método que llama a un método recursivo para
añadir parámetros necesarios de la solución recursiva
public static int sumarArray(int [] aEnteros) { sumarArrayRec(aEnteros,0);
}
public static int sumarArrayRec(int [] aEnteros, int pos){
// Si hemos llegado al final // del array la suma es 0if (pos == aEnteros.length){
return 0;} else{
return aEnteros[pos] + sumarArrayRec(aEnteros, pos+1);
}}
Solución
Es lo que se conoce como
recursividad en concha
Ejercicio 1
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Diseñar un método para visualizar los elementos de un array de enteros.
Con recursividad en concha
public static void visualizarArray(int[] aEnteros) { visualizarArrayRec(aEnteros, aEnteros.length - 1);}
public static void visualizarArrayRec(int[] aEnteros, int pos){
if (pos >= 0) {visualizarArrayRec(aEnteros, pos - 1);System.out.println(aEnteros[pos]);
}}
Solución
Ejercicio 2
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Diseñar un método para visualizar los elementos de un fichero de alumnos(Alumno tiene un método mostrar)
public static void visualizarAlumnos(String nFic) throws Exception{
FileInputStream fis = new FileInputStream(nFic);ObjectInputStream ois =
new ObjectInputStream(fis);visualizarAlumnosRec(ois);ois.close();
}
public static void visualizarAlumnosRec(ObjectInputStream ois) throws Exception{
Alumno a = (Alumno) ois.readObject();if (a != null){
a.mostrar();visualizarAlumnosRec (ois);
}}
Solución
Ahora, a por la
recursividad múltiple
Cuando una función se llama a sí misma
varias veces
La serie de
Fibonaccif(0) = 0f(1) = 1
f(n) = f(n-1) + f(n-2)
Ejercicio 1
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Realizar una función recursiva quecalcule el termino n de la serie deFibonacci
public static int fibonacci(int n){// Caso base primero si el término es 0// entonces es 0if (n == 0){
return 0;}// Caso base segundo si el término es 1 // entonces 1else if (n == 1){
return 1;}// Caso recursivo. Se llama dos veces a la // función recursivaelse{
return fibonacci(n-1) + fibonacci(n-2);}
}
Solución
Ejercicio 2
Ejercicio:Escribir un programa que calcule todos los factoriales del 1 hasta el valor
entero N que se introduce por teclado, el valor de N es mayor de cero.
Diseñar un método para calcular el número combinatorio de “m” elementos tomados de “n” en “n”.
Primera forma de solución:
Cm,n = m! / n!(m-n)!
No tiene recursividad propia
Segunda forma de solución: Iterativa
Cm,n = 1 * (m-1+1) / 1 * (m-2+1) / 2 * ... *(m-i+1) / i
No tiene recursividad
Tercera forma de solución:
Recursividad Directa Simple
si n = 0 Cm,n = 1si n > 0 Cm,n = Cm,n-1 * (m-n+1) / n
public static int combinacionesSimple(int m , int n){if (n == 0){
return 1;}else{
return combinacionesSimple(m, n - 1) * (m – n + 1)/n;
}}
Solución
Cuarta forma de solución:
Recursividad Directa Múltiple
si n = 0 Cm,n = 1si n = m Cm,n = 1si n > m Cm,n = 0si m > n > 0 Cm,n = Cm-1,n + Cm-1,n-1
public static int combinacionesMultiple(int m , int n){
if (n == 0 || m == n){return 1;
}else{
return combinacionesMultiple(m -1 ,n) * combinacionesMultiple(m-1 , n - 1);
}}
Solución
Para entender la recursividad, había que saber
lo qué era la recursividad
La recursividad NO es eficiente
La recursividad proporciona
soluciones elegantes
“Hay pocas virtudes sin prudencia”
-Marco Tulio Cicerón