Page 43 - revista 2019

Revista de la Facultad de Ingeniería, Año 6, Número 1
frase final: “…y usarla para resolver el problema, excepto en los casos tan sencillos en
que no sea necesaria”. Estos “casos base”, que no requieren de recursividad, son los
que hacen posible implementar soluciones recursivas. Deberemos pensar que
tenemos una función que resuelve el problema, pero también deberemos encontrar
casos en que no sea necesaria, y combinando ambos, tendremos la solución buscada.

Algunos ejemplos clásicos

Pasemos a ver algunos ejemplos prácticos de aplicación. Dado que hoy prácticamente
todos los lenguajes de programación soportan recursividad, trabajaremos con el
ubicuo JavaScript, pero en otros lenguajes las diferencias sintácticas serían mínimas.
¿Cómo buscaríamos un valor en un vector (“array”)? (La mejor respuesta sería “usar
funciones .find(), .indexOf(), o .includes(), pero como aquí queremos aplicar
recursividad, ignoraremos tales soluciones obvias.) La lógica es similar a lo que se
hace en la vida real:
 si busco algo, pero ya busqué en todos lados y no lo encontré, fracasé
 si no, buscaré en un primer sitio, y si ahí está, tuve éxito
 y si no lo encontré en ese sitio, deberé buscar en el resto de los lugares en que
puede estar.
Lo interesante de esta descripción, es que se trata de un algoritmo eminentemente
recursivo, pues “buscar en el resto...” se hará lógicamente aplicando el mismo
algoritmo: ver listado 1.

const search = (arr, k) => {
if (arr.length === 0) {
return false;
} else if (arr[0] === k) {
return true;
} else {
return search(arr.slice(1), k);
}
};
Listado 1: Una implementación de búsqueda en un array, recursiva, en
JavaScript. Los dos primeros return corresponden a casos base; el
tercero, a la llamada recursiva.

Consideremos otro problema: ordenar un vector de números. (Nuevamente,
ignoremos que JavaScript provee .sort(); queremos aplicar recursividad contra
viento y marea!) Un algoritmo conocido por su eficiencia es Quicksort:

 si el array es chico (0 ó 1 elementos) no hay nada que hacer;
 si no:
◦ elegir un elemento del array, y llamarlo “pivote”;
◦ particionar los restantes elementos en dos arrays: los valores que son
menores que el pivote, y los que no lo son;
◦ ordenar esos dos arrays recursivamente;
◦ tomar el array (ordenado) con los menores, seguido por el pivote, seguido
por el array (ordenado) con los mayores.

Podemos ver un ejemplo en la figura 2.

42