“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