Descargar

Programación. Recursividad

Enviado por Pablo Turmero


    edu.red “Para entender la recursividad, primero hay que entender lo qué es la recursividad” -Un programador anónimo ? Hello world

    edu.red La recursividad consiste en definir una entidad en función de sí misma

    edu.red Podemos definir recursivamente Tipos de datos Problemas

    edu.red Definamos un tipo de datos de manera recursiva: clase Nodo Object elemento Nodo siguiente

    edu.red Ejemplo de recursividad de tipos: Nodo public class Nodo{ private Object elemento; private Nodosiguiente; // Seguiría la definición … }

    edu.red Ahora, a por la difícil: recursividad de ejecución o recursividad de problema

    edu.red La recursividad de ejecución es la posibilidad de definir un problema en función del propio problema

    edu.red Dicho de otro modo: una función que dentro de su código se llama … ¡A SÍ MISMA!

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red Para que una función pueda ser recursiva tienen que cumplirse ciertos requisitos:

    edu.red Que pueda definirse en términos de sí misma

    edu.red Que exista un criterio de finalización o “caso base”

    edu.red public static int funcionRec(int n){ if (n == 0){ return 1; } else{ return n * funcionRec(n-1); } } Es el caso base

    edu.red Que en cada llamada recursiva se esté más cerca de cumplirse el Caso Base

    edu.red 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

    edu.red Que se resuelva el problema en un tiempo limitado o finito

    edu.red Un ejemplo mítico: el cálculo del factorial de un número x!

    edu.red 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)!

    edu.red 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

    edu.red Haced la solución recursiva del procedimiento de cálculo del factorial de un número

    edu.red 1 Definimos el caso base public static int factorial(int n){ if (n == 0){ return 1; } } El factorial de 0 es 1

    edu.red 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); } }

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red public static double potencia(double base, int exp){ if (exp == 0) return 1; else return (base * potencia(base, exp – 1)); } Solución recursiva

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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

    edu.red 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.

    edu.red 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

    edu.red ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN LA VERSIÓN DE DESCARGA