Recursividad – Monografias.com
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