Estructuras de Datos: Tema 2: Pilas y Colas. Anexo. Recursividad

Estructuras de Datos
Tema 2: Pilas y Colas.

Anexo. Recursividad
Pilas y colas 2
Recursividad
1. Concepto de recursividad.
2. Ejemplos de métodos recursivos.
3. Tipos de recursividad.
4. Recursivo vs iterativo.
Pilas y colas > Recursividad 3
1. Concepto de recursividad
 Un objeto es recursivo cuando forma parte de si mismo o de
su propia definición.
 En matemáticas se usa para algunas definiciones:
• Definición de número natural:
o El 1 es un número natural.
o El siguiente de un número natural es un número natural.
• Definición de factorial de un número:
o El factorial de 0 es 1: 0! = 1
o El factorial de N es N! = N * (N-1)!
• Sucesión de Fibonacci:
o f (0) = 1;
o f (1) = 1;
o Para n > 1, f (n) = f (n-1) + f (n-2)
1. Concepto de recursividad
 Recursividad en programación:
• Una función es recursiva cuando se llama a si misma.
• Un tipo de datos es recursivo cuando forma parte de su propia
definición.
• Planteamiento:
o Se descompone el problema en subproblemas más pequeños.
o Se localiza el caso más básico.
o Se identifica el camino para llegar al caso base haciendo una o varias
llamadas recursivas.
• Ejecución:
o Al menos una de las instrucciones de la función será una llamada a la
misma función.
o Se irán ejecutando copias de la función hasta que se alcance la condición
de fin de recursividad: caso base.
o Al finalizar cada llamada se retorna al punto donde se realizó la llamada
anterior.
2. Ejemplos de métodos recursivos

 Ejemplo 1: Método factorial.
• Definición:
o El factorial de 0 es 1: 0! = 1
o El factorial de N es N! = N * (N-1)!
• Caso básico (Condición de parada): dato <= 1
• Se calcula el factorial del número anterior, y a la vuelta de la
recursividad, se devuelve el valor al punto donde se realizó la
llamada
public static long factorial (int dato) {
long resultado = 1;
if (dato > 1)
resultado = dato * factorial (dato - 1);
return resultado;
}

 Ejemplo 1. Llamada desde el main:
import java.util.Scanner;
public class Factorial {
public static void main (String [] args) {
int dato;
long factorial;
Scanner teclado = new Scanner(System.in);
System.out.print ("Introduzca un número: ");
dato = teclado.nextInt();
factorial = factorial (dato);
System.out.println("Resultado: "+factorial);
}
//método factorial
}

 Funcionamiento
public static long factorial (int dato) {
long resultado = 1;
if (dato > 1)
resultado = dato * factorial (dato - 1);
return resultado;
}
 Para dato = 4:
dato = 4 (dato>1)
resultado=dato*factorial(dato-1)
resultado = 4*6 = 24
dato = 3 (dato>1)
resultado = 3*2 = 6
dato = 2 (dato>1)
resultado = 2*1 = 2
dato = 1
resultado = 1

 Ejemplo 2. Escribir un número decimal en binario:
• Para pasar el número a binario, hay que tener en cuenta los siguientes
casos:
o Caso base: si n < 2, en binario es n
o Si n >= 2, n en binario es n/2 seguido de n%2
o Hay que escribir los números a la vuelta de la recursividad
• Método escribirEnBinario:
public static void escribirEnBinario (int número) {
if (número >= 2) {
escribirEnBinario (número / 2);
System.out.print (número % 2);
}
else System.out.print (número);
}

 Ejemplo 2. Clase completa:
public class PruebasRecursividad {
public static void escribirEnBinario(int número) {
if (número >= 2) {
escribirEnBinario(número / 2);
System.out.print(número % 2);
} else System.out.print(número);
}
public static void main(String[] args) {
int dato;
System.out.print("Introduzca un número: ");
System.out.print("En binario: ");
escribirEnBinario(dato);
System.out.println("\n\t\t\t" + Integer.toBinaryString(dato));
}
}
• Resultado de la ejecución:

 Ejemplo 2 (b). Devolver como resultado del método un
String que contenga el número decimal en formato binario:
public class PruebasRecursividad {
public static String hacerStringBinario (int número) {
String binario="";
if (número >= 2) {
binario = hacerStringBinario(número / 2)+(número % 2);
} else binario = binario+número;
return binario;
}
public static void main(String[] args) {
int dato;
long factorial = 1;
System.out.print("Introduzca un número: ");
System.out.print ("En binario: 1. “ + Integer.toBinaryString(dato));
String binario = hacerStringBinario (dato);
System.out.println ("\t\t\t2. " + binario);
}
}

 Ejemplo 3. Escribir los n primeros números de la serie de
Fibonacci.
• Haremos un método recursivo que calcula el valor del enésimo número
de la serie:
o Si n = 0 o n = 1, f (n) = 1;
o Para n > 1, f (n) = f (n-1) + f (n-2)
public static int fibonacci (int número){
int resultado = 1;
if (número >1)
resultado = fibonacci(número-1) + fibonacci(número-2);
return resultado;
}
• Y otro iterativo que escriba los n primeros números
public static void escribirFibonacci (int n) {
for (int i = 0; i < n; i++)
System.out.print (" "+fibonacci(i));
}

 Ejemplo 3. Escribir los n primeros números de la serie de
Fibonacci.
• También podemos hacer escribirFibonacciRecursivo
public static int fibonacci (int número){
int resultado = 1;
if (número >1)
resultado = fibonacci(número-1) + fibonacci(número-2);
return resultado;
}
public static void escribirFibonacciRecursivo (int n) {

if (n > 0) {
int aux = fibonacci(n - 1);
escribirFibonacciRecursivo(n-1);
System.out.print(" " + aux);
}
}
3. Tipos de recursividad
 Recursividad directa:
• Se realizan llamadas a la misma función recursiva que se está
diseñando.
• A su vez puede ser:
o Simple: Solo existe una llamada recursiva dentro de la función (factorial)
o Múltiple: Se realiza más de una llamada recursiva (fibonacci)
o Anidada: la llamada recursiva aparece como un parámetro dentro de
otra llamada
 Recursividad mutua o indirecta:
• El método llama a otro u otros métodos, y en el último método
se vuelve a llamar al primero
 Ejemplo de recursividad anidada:
• Función de Ackermann
public static int ackermann (int m, int n) {

int resultado;
if (m == 0)
resultado = n + 1;
else if (m > 0 && n == 0)
resultado = ackermann (m-1, 1);
else resultado = ackermann (m-1, ackermann (m, n-1));
return resultado;
}
 Ejemplo de recursividad mutua o indirecta:
• Comprobar si un número es par o impar recursivamente
public static boolean esPar (int n) {
boolean resul = true; El método esPar
if (n != 0) llama al método
resul = esImpar(n - 1); esImpar
return resul;
}
private static boolean esImpar (int n) {

boolean resul = false;
if (n != 0)
resul = esPar(n - 1);
return resul;
} Y el método esImpar
llama al método esPar
4. Recursivo vs iterativo
• Comparativa entre ambos tipos de algoritmo. Ejemplo

factorial
o Recursivo
public static long factorial(int dato) {
long resultado = 1;
if (dato > 1)
resultado = dato * factorial(dato - 1);
return resultado;
}
o Iterativo
public static long factorialIterativo (int dato) {
long factorial = 1;
for (int i = 1; i <= dato; i++)
factorial = factorial * i;
return factorial;
}
• Comparativo entre ambos tipos de algoritmo
• Recursivo • Iterativo
o Mayor uso de memoria o Menor uso de memoria
o Mayor tiempo de ejecución o Menor tiempo de ejecución
o Código mucho más simple o Código más largo
o Posibilidad de marcha atrás o No hay posibilidad de marcha
• se puede realizar parte del atrás
tratamiento antes de la llamada
recursiva, y parte después
• se pueden mostrar los datos y
resultados antes y después de
la recursividad
o Los algoritmos de backtracking
y divide y vencerás son más
sencillos de forma recursiva.
• Cuándo usar recursividad

o Si el problema a resolver se puede definir de forma recursiva
o Si los datos que se van a utilizar son datos recursivos
o Si se necesita utilizar los datos a la vuelta (por ejemplo el método
escribirEnBinario)
o Si se van a realizar algoritmos de backtracking o divide y vencerás
o No es conveniente cuando se necesitan llamadas múltiples
o Es necesario definir muy claramente la condición de parada (caso
base) para evitar provocar bucles infinitos

Estructuras de Datos: Tema 2: Pilas y Colas. Anexo. Recursividad

Cargado por

Copyright:

Formatos disponibles

Estructuras de Datos: Tema 2: Pilas y Colas. Anexo. Recursividad

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Estructuras de Datos: Tema 2: Pilas y Colas. Anexo. Recursividad

Cargado por

Copyright:

Formatos disponibles

Estructuras de Datos

Tema 2: Pilas y Colas.

2. Ejemplos de métodos recursivos

2. Ejemplos de métodos recursivos

2. Ejemplos de métodos recursivos

2. Ejemplos de métodos recursivos

2. Ejemplos de métodos recursivos

2. Ejemplos de métodos recursivos

2. Ejemplos de métodos recursivos

2. Ejemplos de métodos recursivos

public static void escribirFibonacciRecursivo (int n) {

public static int ackermann (int m, int n) {

private static boolean esImpar (int n) {

• Comparativa entre ambos tipos de algoritmo. Ejemplo

• Comparativo entre ambos tipos de algoritmo

• Cuándo usar recursividad

También podría gustarte