Programación bit a bit: Recursividad y Divide y Vencerás
Ahora que hemos dado lo más básico de la programación podemos llegar a situaciones donde resolver un problema en particular puede llegar a resultar bastante complicado. Un problema modelo es el de ordenar un vector de números. Para tamaños pequeños no hay problema, pero para tamaños de vector muy grande es necesario buscar una forma más eficiente de hacerlo. Por ello el artículo de hoy trata sobre la recursividad y el algoritmo Divide y Vencerás Igual que hacemos siempre, el artículo de hoy viene con el siguiente código:
package net.openwebinars;
public class Recursividad {
static int[] ordenarVector(int p, int q, int[] v) {
final int N = Math.abs(p - q) + 1;
int[] result = new int[N];
// Caso Base
if (Math.abs(p - q) == 1) {
if (v[p] > v[q]) {
result[0] = v[q];
result[1] = v[p];
} else {
result[0] = v[p];
result[1] = v[q];
}
} else { // Subproblemas
int[] izq = ordenarVector(p, (p + q) / 2, v);
int[] der = ordenarVector(((p + q) / 2) + 1, q, v);
result = combinar(izq, der, N);
}
return (result);
}
static int[] combinar(int[] izq, int[] der, final int N) {
int i = 0;
int j = 0;
int k = 0;
int[] result = new int[N];
while ((i != izq.length) && (j != der.length)) {
if (izq[i] < der[j]) {
result[k] = izq[i];
i++;
} else {
result[k] = der[j];
j++;
}
k++;
}
if (i != izq.length) {
while (i != izq.length) {
result[k] = izq[i];
k++;
i++;
}
} else {
while (j != der.length) {
result[k] = der[j];
k++;
j++;
}
}
return (result);
}
public static void main(String[] args) {
int[] vector = {5, 9, 1, 10, 7, 3, 8, 4};
vector = ordenarVector(0, vector.length - 1, vector);
for (int i = 0; i != vector.length; i++)
System.out.print(vector[i] + " ");
System.out.println();
}
}
Nota: la función Math.abs() devuelve el valor absoluto de una expresión. En matemáticas sería equivalente a hacer |2 - 3| = 1
Recursividad
"Para entender la recursividad, primero hay que entender la recursividad" Esa frase resulta redundante , ¿verdad? Si te has dado cuenta de ello, has entendido en gran medida la recursividad. Podemos entender que un algoritmo es recursivo cuando el problema que resuelve se obtiene su solución resolviendo el mismo problema en instancias más pequeñas usando el mismo algoritmo en cada una de ellas. Resulta bastante complicado de entender así que voy a poner el siguiente ejemplo:
static int multiplicar(int x, int y) {
int resultado = 0;
if (y == 0) {
resultado = 0;
} else {
resultado = x + multiplicar(x, y - 1);
}
return (resultado);
}
Esa función lo que hace es multiplicar el número x por el número y sin utilizar el operador *. Si nos fijamos en la siguiente línea:
resultado = x * multiplicar(x, y - 1);
vemos que estamos llamando de nuevo a la función multiplicar, aunque disminuyendo el valor de y en una unidad. Debido a esa acción de volver a llamar a la función multiplicar decimos que es un algoritmo recursivo. Otro ejemplo:
static void mostrarContenido(int p, int[] vector) {
if (p != vector.length) {
mostrarContenido(p + 1, vector);
System.out.println(vector[p]);
}
}
En esta ocasión, el procedimiento mostrarContenido muestra el contenido de un vector desde el último elemento hasta el primero, a pesar de que se empieza a recorrer desde el primer elemento. Viendo los dos ejemplos podemos establecer que los algoritmos recursivos siguen generalmente una estructura:
nombreFuncion(tipoArgumento1 argumento1, tipoArgumento2 argumento2, ..., tipoArgumentoN argumentoN) {
si (casoBase) {
// Fin de la recursión
} sino {
// Llamada recursiva
}
}
Esta estructura es flexible ; si se fijan en mi segundo ejemplo no tengo un caso base o condición de parada explícito, pero sí implícito. En general, los algoritmos recursivos se pueden implementar de manera iterativa . Se dice que un algoritmo es iterativo cuando se ejecutan cada una de sus fases una seguida de la siguiente hasta una condición de parada (normalmente se implementan utilizando un bucle for). Los dos ejemplos utilizados implementados de forma iterativa serían de la siguiente forma:
static int multiplicar(int x, int y) {
int resultado = 0;
for (int i = 0; i != y; i++)
resultado += x;
return (resultado);
}
static void mostrarContenido(int[] vector) {
for (int p = vector.length; p != -1; p--)
System.out.println(vector[p]);
}
La principal diferencia entre un algoritmo recursivo y uno iterativo es que el primero utiliza la pila de proceso en la cual guardan el estado actual de las variables al llamar a la función recursiva. Si no sabes qué es una pila no te preocupes, más adelante intentaremos implementar una. Es cierto que la recursión como tal no es una técnica para resolver por si sola problemas de gran tamaño. Para ello tenemos la técnica de Divide y Vencerás
Divide y Vencerás
Divide y Vencerás es una técnica algorítmica la cual nos permite resolver problemas dividiendo el problema original en subproblemas más pequeños. Su estructura es la siguiente:
nombreFuncion(tipoArgumento1 argumento1, tipoArgumento2 argumento2, ..., tipoArgumentoN argumentoN) {
si (casoBase) {
// Fin de la recursión
} sino {
// Llamadas recursivas
// Combinación de subproblemas
}
}
De forma similar a la estructura de la recursividad, DyV añade una fase más de combinación en la cual se "combinan" los resultados obtenidos de los subproblemas en los cuales se ha dividido el problema original. El código de hoy es una implementación del algoritmo Merge Sort .
Merge Sort
El Merge Sort es un algoritmo el cual utiliza la técnica DyV para ordenar los elementos de un vector. Su algoritmo explicado es el siguiente:
MergeSort(p, q, vector) {
// Caso Base
si (|p - q| == 1) {
//Intercambiamos (si hace falta) los elementos
//del subvector de tamaño 2
} sino {
subvectorIzquierdo = MergeSort(p, (p + q) / 2, vector);
subVectorDerecho = MergeSort((p + q) / 2 + 1, q, vector);
resultado = combinar(subvectorIzquierdo, subVectorDerecho);
}
return (resultado);
}
Una explicación más clara de cómo funciona la podemos ver en el siguiente gif: 
Como pueden ver la idea es siempre la misma: mientras el vector tenga tamaño mayor que 2, subdividirlo en dos subvectores por la mitad teniendo así vectorIzquierdo y vectorDerecho. Ordenar ambos subvectores y posteriormente, combinarlos entre ellos. En el código de hoy vemos he separado la fase de combinar en otra función para que quedase más claro el algoritmo, pero aunque vean algún que otro bucle while, la idea es la explicada anteriormente tanto en texto como en el gif.
¿Subproblemas repetidos?
La técnica DyV plantea un problema: en ocasiones al intentar resolver un subproblema nos damos cuenta de que ese subproblema ya se resolvió anteriormente. Si no controlamos ese aspecto puede ocurrir que un mismo subproblema se calcule y se resuelva tantas veces como aparezca, lo que supone un esfuerzo extra innecesario. Generalmente hay dos formas de solucionar esto:
- Definir bien el caso base; un buen caso base ayuda a que los subproblemas se repitan menos
- Añadirle al algoritmo " memoria "; guardar en alguna estructura externa la solución de anteriores subproblemas para que cuando se repitan consultar dicha estructura y no repetir todo el proceso
Para finalizar el artículo de hoy decir que si bien DyV es una técnica muy útil, normalmente lo complicado no es implementar un algoritmo, sino busca la forma de dividir el problema en subproblemas más fáciles de resolver (si la hay). Y hasta aquí llegamos con el capítulo de hoy. No se olviden de que tienen a su disposición el curso de la asignatura en el apartado de cursos online donde pueden hacer ejercicios y/o cuestionarios a modo de autoaprendizaje. No duden en preguntar todo aquello que no entiendan y espero verles en el próximo artículo donde aprenderemos a darle más clase a nuestros programas. ¡Un saludo!
Listado de capítulos
En esta sección se listan todos los capítulos de este pequeño curso:
