Recursividad
La recursividad consiste en definir una entidad en función de si misma
En programación la recursividad nos da la posibilidad de definir un tipo de datos en función de si mismo, o bien nos permite definir un problema en función de si mismo.
Recursividad de Definición: aplicada a Estructuras de Datos
Posibilidad de definir un tipo de datos en términos de si mismo.
public class Nodo {
protected Object elemento;
protected Nodo siguiente;
public Nodo()
/* Crea un nuevo objeto nodo */
{ }
…
}
Recursividad de Ejecución : aplicada a los problemas
Posibilidad de definir un problema en función del propio problema.
Recursividad de Ejecución o Recursividad Funcional
Es aquella que se aplicada a la solución de los problemas y define el problema en función del propio problema, lo cual consiste en que método puede llamarse así mismo una o varias veces.
En la recursividad de ejecución se distingue:
a) Recursividad Directa: Consiste en que un método se llama a si mismo desde uno (recursividad simple) ó varios puntos del código (recursividad múltiple).
b) Recursividad Indirecta o Mutúa: Consiste en que dos métodos se llaman entre si, es decir, mutuamente.
Para poder implementar un método de forma recursiva, es necesario que se cumplan las siguientes condiciones:
a) Que pueda definirse en términos de si mismo.
b) Que exista un criterio de finalización, llamado Caso Base, llegado el cual no se aplique de nuevo la llamada recursiva.
c) Que en cada llamada recursiva se este más cerca de que se cumpla el Caso Base.
d) Que se resuelva el problema en un tiempo limitado o finito.
Un ejemplo claro de método recursivo es el calculo del factorial de un numero entero N, que puede definirse de forma recursiva o de forma iterativa.
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.
Ejemplo de una ejecución:
Introduce un numero: -4
Introduce un numero: 0
Introduce un numero: 4
1! = 1
2! = 1 * 2 = 2
3! = 1 * 2 * 3 = 6
4! = 1 * 2 * 3 * 4 = 24
public class CalculoDelFactorial
Solucion Iterativa:
public class CalculoDelFactorial
Solucion Recursiva:
public class CalculoDelFactorial
Ejercicio:
Diseñar un método que calcule la potencia de un numero real elevado a
un entero.
Solucion Iterativa:
public static double potencia(double base, int exp)
{
double pot = 1;
for (int i=1; i<= exp; i++)
{
pot = pot * base;
}
return pot;
}
Solucion Recursiva:
public static double potencia(double base, int exp)
{
if (exp == 0)
return 1;
else
return (base * potencia(base, exp – 1));
}
Ejercicios:
1.- Escribir un método que calcule la suma de los N primeros números naturales.
N = 5 ( 1 + 2 + 3 + 4 + 5 = 15
N = 5 ( 5 + 4 + 3 + 2 + 1 = 15
Suma (N) ( N + Suma(N-1)
2.- Escribir un método que visualice los N primeros números naturales del 1 al N.
N = 4 ( visualiza los numeros 1
2
3
4
3.- Escribir un método que visualice los N primeros números naturales del N al 1.
N = 4 ( visualiza los numeros 4
3
2
1
4.- Escribir un método que visualice los dígitos de un número natural N al revés
N = 7815 ( visualizar el numero 5187
5.- Escribir un método que visualice los dígitos de un número natural N, uno por línea.
N = 7815 ( visualizar el numero 7
8
1
5
6.- Escribir un método que sirva para subrayar un texto.
Ejercicios:
1.- Escribir un método que calcule la suma de los N primeros números naturales.
public static int suma(int n) version 1
{
if (n == 0)
return 0;
else
return (n + suma(n – 1));
}
public static int suma(int n) version 2
{
if (n == 1)
return 1;
else
return (n + suma(n – 1));
}
2.- Escribir un método que visualice los N primeros números naturales del 1 al N.
public static void visualiza(int n)
{
if (n > 0)
{
visualiza(n-1);
System.out.println(n);
}
}
3.- Escribir un método que visualice los N primeros números naturales del N al 1.
public static void visualiza(int n)
{
if (n > 0)
{
System.out.println(n);
visualiza(n-1);
}
}
4.- Escribir 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)
{
if (n < 10)
{
System.out.println(n);
}
else
{
System.out.print(n % 10);
visualizarDigitosReves(n / 10);
}
}
5.- Escribir un método que visualice los dígitos de un número natural N, uno por linea.
N = 7815 ( visualizar el numero 7
8
1
5
public static void visualizarDigitos(int n) {
if (n < 10)
System.out.println(n);
else
{
int digito = n % 10 ;
visualizarDigitos(n / 10);
System.out.println(digito);
}
}
6.- Escribir un método que sirva para subrayar un texto.
public static void subrayar(int longitud) {
if (longitud > 0) {
System.out.print("_");
subrayar(longitud-1);
}
}
Ejercicio Recursividad en concha
Dado el siguiente programa Java diseñar un método para sumar los elementos
de un vector de enteros.
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
int suma =sumarArray( vNumeros);
System.out.println(suma);
}
public static int sumarArray(int [] a)
{
…
}
Solucion Iterativa
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
int suma = sumarArray( vNumeros);
System.out.println(suma);
}
public static int sumarArray(int [] a)
{
int acumulador = 0;
for (int pos=0; pos < a.length; pos++)
{
acumulador = acumulador + a[pos];
}
return acumulador;
}
Solucion Recursiva _1 ( Recorre el array desde el principio hacia el final
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
int suma = sumarArray( vNumeros);
System.out.println(suma);
}
public static int sumarArray(int [] a)
{
return sumarArrayRec(a, 0);
}
public static int sumarArrayRec(int [] a, int pos) {
if (pos == a.length)
return 0;
else
return a[pos] + sumarArrayRec(a, pos + 1);
}
Solucion Recursiva_2 ( Recorre el array desde el final hacia el principio
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
int suma = sumarArray( vNumeros);
System.out.println(suma);
}
public static int sumarArray(int [] a) {
return sumarArrayRec(a, a.length-1);
}
public static int sumarArrayRec(int [] a, int pos) {
if (pos < 0)
return 0;
else
return a[pos] + sumarArrayRec(a, pos – 1);
}
Solucion Recursiva_3 ( Recorre el array desde el final hacia el principio
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
int suma = sumarArray( vNumeros);
System.out.println(suma);
}
public static int sumarArray(int [] a) {
return sumarArrayRec(a, a.length-1);
}
public static int sumarArrayRec(int [] a, int pos) {
if (pos == 0)
return a[pos];
else
return a[pos] + sumarArrayRec(a, pos – 1);
}
Ejercicio Recursividad en concha
Dado el siguiente programa Java diseñar un método para visualizar los
elementos de un vector de enteros.
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
visualizarArray( vNumeros);
}
public static void visualizarArray(int [] a)
{
…
}
Solución Iterativa
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
visualizarArray( vNumeros);
}
public static void visualizarArray(int [] a)
{
for (int pos=0; pos < a.length; pos++)
{
System.out.println(a[pos]);
}
}
Solución Recursiva_1 ( Visualiza los elementos del principio hacia el final
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
visualizarArray( vNumeros);
}
public static void visualizarArray(int [] a)
{
visualizarArrayRec(a, 0);
}
public static void visualizarArrayRec(int [] a, int pos)
{
if (pos < a.length)
{
System.out.println( a[pos] );
visualizarArrayRec(a, pos + 1);
}
}
Solución Recursiva_2 ( Visualiza los elementos del principio hacia el final
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
visualizarArray( vNumeros);
}
public static void visualizarArray(int [] a)
{
visualizarArrayRec(a, 0);
}
public static void visualizarArrayRec(int [] a, int pos)
{
if (pos < a.length)
{
System.out.println( a[pos] );
visualizarArrayRec(a, pos + 1);
}
}
Solución Recursiva_3 ( Visualiza los elementos del final hacia el principio
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
visualizarArray( vNumeros);
}
public static void visualizarArray(int [] a)
{
visualizarArrayRec(a, a.length-1);
}
public static void visualizarArrayRec(int [] a, int pos)
{
if (pos == 0)
System.out.println( a[pos] );
else
{
System.out.println( a[pos] );
visualizarArrayRec(a, pos – 1);
}
}
Ejercicio Recursividad en concha
Dado el siguiente programa Java diseñar un método para visualizar los
elementos de un fichero de alumnos..
public static void main(String[] args)
{
int [] vNumeros = {1, 3, 5, 7, 9, 11, 13};
visualizarArray( vNumeros);
}
public static void visualizarArray(int [] a)
{
…
}
public static void main(String[] args)
{
leerFichero( "ALUMNOS.DAT");
}
public static void leerFichero(String nomFich) throws Exception
{
FileInputStream fis = new FileInputStream(nomFich);
ObjectInputStream ois = new ObjectInputStream(fis);
LeerFicheroRec(ois);
Ois.close();
}
public static void leerFicheroRec(ObjectInputStream ois) throws Exception
{
Alumno alu = (Alumno) ois.readObject();
if (alu != null)
{
leerFicheroRec(ois);
alu.mostrar();
}
}
Ejercicio: Recursividad Múltiple
Realizar una función recursiva que calcule el término N de la serie de Fibonacci:
1, 1. 2, 3, 5, 8, 13, 21, … ( Fibonacci(N) = Fibonacc (N-1) + Fibonacc (N-2)
caso base: (N < 2) ( Fibonacci = n
caso recursivo: (N >= 2) ( Fibonacci(N)= Fibonacci(N-1) + Fibonacci(N-2)
public static int fibonacci( int n )
{
if (n < 2)
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
}
La secuencia de llamadas para calcular el termino 6 de la serie de Fibonacci sera:
Fib(6)
_______________________________________
Fib(5) Fib(4)
__________________________ ______________
Fib(4) Fib(3) Fib(3) Fib(2)
________________ __________ __________
Fib(3) Fib(2) Fib(2) Fib(1) Fib(2) Fib(1)
____________
Fib(2) Fib(1)
Fib(5) ( Se llama desde el propio método 1 vez
Fib(4)( Se llama desde el propio método 2 veces
Fib(3)( Se llama desde el propio método 3 veces
Fib(2)( Se llama desde el propio método 5 veces
Fib(1)( Se llama desde el propio método 3 veces
Ejercicios Recursividad
Diseñar un método para calcular el número combinatorio de "m" elementos tomados de "n" en "n".
Este problema deberéis resolverlo aplicando diferentes métodos:
1.- Aplicando la formula que hace uso del calculo del factorial
Cm,n = m! / n!(m-n)!
2.- Aplicando la formula iterativa: para i ( de 1 a n
Cm,n = 1 * (m-1+1) div 1 * (m-2+1) div 2* … *(m-i+1)div I
3.- Aplicando la ley de recurrencia utilizando la recursividad Directa Simple:
caso base: si n = 0 Cm,n = 1
caso general: si n > 0 Cm,n = Cm,n-1 * (m-n+1) div n
4.- Aplicando la ley de recurrencia utilizando la recursividad Directa Múltiple
casos base: si n = 0 Cm,n = 1
si n = m Cm,n = 1
si n > m Cm,n = 0
caso general: si m > n > 0 Cm,n = Cm-1,n + Cm-1,n-1
La llamada al subprograma NumeroCombinatorio para todos los casos podría ser:
Enviado por:
Pablo Turmero