“Para entender la recursividad, primero hay que entender lo qué es la recursividad” -Un programador anónimo ? Hello world
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 elemento Nodo 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! = 1 Si 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 * 3 2 2 * 1 1 * 0 1 6
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 0 if (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 1 if (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 1 visualizarNumerosDesdeN(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
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN LA VERSIÓN DE DESCARGA