RECURSIVIDAD
Recursividad: Es una técnica
de programación que consiste en subdividir un algoritmo en la respuesta final y
la resolución del resto de los datos con el mismo algoritmo. Aunque no es muy
elegante, también se puede decir que la recursividad consiste en implementar
una solución que se llama a símisma. Sin embargo lo importante es tener claro
que esto se utiliza para descomponer los datos de entrada del problema e
implementarlos como subproblemas del mismo.
Implementación:
Básicamente la implementación consta de un borde o condición de término y la
implementación de la solución para el resto de los datos.
Pseudocódigo:
funcion recursiva (parámetros){
si (borde) termina;
si no recursiva (nuevos parámetros);
}
Ej: La función
factorial se define como:
... ¿No se
entiende?... ¡Qué vergüenza!
Ok. Lo explico menos
engorrosamente:
En palabras, se
expresa como: “El factorial de un número
es el resultado de la multiplicación de dicho número con la multiplicación de
todos sus antecesores naturales”.
Se supone que la
función factorial es una función para números naturales, sin embargo por varias
razones se llegó a la convención de que el factorial de cero es uno, por lo que
podemos redefinir la función como:
En esta última
expresión vemos cómo el problema se subdivide en forma recursiva.
Ahora vamos a
implementarla en java.
public int factorial (int
n){
if (n==0) return 1;
return n * factorial(n-1);
}
Este ejemplo es
bastante sencillo, y puede que hasta poco útil, pero es un ejemplo pequeño para
ir calentando motores con la implementación de algoritmos recursivos.
Nota: recordemos que una vez ejecutado un return ya no se siguen
ejecutando las siguientes instrucciones.
Ejercicio propuesto:
Hacer la traza de la función anterior para cualquier número mayor que 5 (sólo
para que tenga una dificultad moderada).
Ejercicios Resueltos:
Implementar en Java
los siguientes algoritmos en forma recursiva:
1.-
Calcular la división entera: Se define división entera como “Contar las veces
que se puede restar un número natural con otro hasta que el sustraendo sea
mayor que el minuendo”.
Ejemplo práctico:
División entera de 48 y 11:
En este caso el
resultado es 4, es decir, 4 veces se pudo realizar la resta. No confundir con
el 4 que aparece como resultado de la última resta ya que ese es el resto de la
división.
Comprobación:
Ahora la
implementación en Java:
public int divisionEntera
(int a, int b){
if (b > a) return 0;
return divisionEntera(a – b,b)+1;
}
Ejercicio propuesto:
Hacer la traza de la función anterior.
2.- Convertir
un entero a binario: Para convertir un entero decimal a cualquier base, éste se
divide con la base consecutivamente hasta que el divisor es cero; una vez
terminada esta operación se deben concatenar todos los restos de las
operaciones desde el último hasta el primero. Debido a esto la salida de
nuestra función será un string.
Ejemplo práctico:
Convertir a string binario el número 777.
Una vez terminadas
las divisiones se concatenan los restos de atrás hacia adelante (o de abajo
hacia arriba en este caso).
Resultado = “1100001001”
Implementación en Java:
public String binario (int
n){
if (n == 0) return “”;
if (n%2 == 0) return
binario(n/2)+”0”;
return binario(n/2)+”1”;
}
3.- Multiplicación
rusa: Los rusos multiplican de una manera muy peculiar. Se ponen los múltiplos
como cabeceras de dos columnas. Simultáneamente a uno de los números lo
multiplican por 2 y al otro lo dividen por 2. Esto se repite hasta que el
número que está siendo dividido llega a 1. Luego se toman los valores de la
columna multiplicada y se suman sólo aquellos que en su contra parte tengan un
número impar.
Implementación en Java:
public int rusa (int a, int
b){
if (b == 1) return a;
if (b%2 == 0) return rusa(a*2,b/2);
return a+rusa(a*2,b/2);
}
