04aRecursividad

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 problemasy 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 dosmé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 cumplael 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.




Solución Iterativa  Si X >= 0 X! = 1 * 2 * 3 * 4 * ... * X

Solución Recursiva  Si X = 0 X! = 1
Si X > 0 X! = X *(X-1)!




Solución Iterativa Solución Recursiva

public static int factorial(int x) public static int factorial(int x)
{ {
int fact = 1; if (x == 0)
for (int i=1; i<= x; i++) return 1;
{ else
fact = fact * i; return (x * factorial(x – 1));
} }
return fact;
}
Ejercicio:
Escribir un programa que calcule todos los factoriales del 1hasta 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
{
public static int factorial(int x)
{
…
}

public static void main(String[] args)
{int n = 0;
do{
System.out.print("Introduzca un numero: ");
n = Utilidades.leerEntero();
} while ( n < 1);
System.out.println();
for (int i=1; i<= n; i++)
{
System.out.print(i + "! = ");
for (int j=1; j < i; j++)
{
System.out.print(j + " * ");
}
System.out.println(i + " = " + factorial(i));
}
}
}
Solucion Iterativa:


public classCalculoDelFactorial
{
public static int factorial(int x)
{
int fact = 1;
for (int i=1; i<= x; i++)
{
fact = fact * i;
}
return fact;
}

public static void main(String[] args)
{
public static void main(String[] args)
{
int n = 0;
do{
System.out.print("Introduzca un numero: ");
n = Utilidades.leerEntero();
} while ( n < 1);System.out.println();
for (int i=1; i<= n; i++)
{
System.out.print(i + "! = ");
for (int j=1; j < i; j++)
{
System.out.print(j + " * ");
}
System.out.println(i + " = " + factorial(i));
}
}
}
Solucion Recursiva:


public class CalculoDelFactorial
{
public static int factorial(int x)
{
if (x == 0)
return 1;
else
return (x * factorial(x – 1));
}

public...