Jugando con la recursion 1

Tiempo de lectura: 20 minutos

Lenguaje de programación usado: javascript

Que es recursión?

Algo es recursivo cuando puede definirse en términos de si mismo. Por ejemplo: Imagínese un conejo que se saca a si mismo de un sombrero. Puede parecer ilógico y contra intuitivo que un conejo sea capaz de empujarse a si mismo pero esto es debido a las leyes de la física, que dicen que un cuerpo no puede imprimir una fuerza neto sobre si mismo, no de la lógica. Como se vera mas adelante, las matemáticas y la computación son terreno fértil para la recursion, y con un poco de práctica la confusión inicial que causa desaparecerá.

El ejemplo clásico en matemáticas es el factorial , cuya definición es la siguiente:

Para números naturales:

El factorial de 0 es 1

El factorial de cualquier numero n diferente de 0 es el producto de ese numero y el factorial de su antecesor n-1

Nota la elegancia y brevedad con la que se expresa esta operación, sin una notación complicada y tan simple que cualquiera puede obtener el factorial de un numero, siempre que sea capaz de calcular productos.

En este post se explorara el uso de expresiones de este tipo para encontrar soluciones alternativas a algunos problemas clásicos y se analizaran sus ventajas y desventajas.

Recursion y programación

En programación, la recursión o recursividad puede definirse como la declaración de métodos recursivos. Es ampliamente usada en diseño de algoritmos, especialmente los llamados divide y vencerás, que dividen el problema en partes mas simples y repiten el proceso-por medio de la recursión- hasta que se encuentran con un problema muy simple, La recursión también es un concepto fundamental en programación funcional, paradigma  que ha cobrado relevancia en los últimos anos, tanto que la mayoría de lenguajes de programación se han apresurado a añadir características que permiten implementarlo, o al menos simularlo. Retomando el ejemplo del factorial se implementa una solución en javascript:

function factorial(natural){

if(natural==0)

return 1;

else return natural*factorial(natural-1);

}

Aquí se ha obviado el código que verifica que el argumento de la función sea natural para resaltar la esencia del código. Note se que simple y clara es la expresión, que incluso podría reducirse a un renglón:

function factorial(natural){

return    natural  ?  ( natural * factorial( natural-1 ) )  :  1  ;

}

Hagamos una prueba de escritorio para verificar que funciona correctamente:

Supóngase que se quiere encontrar el factorial de 3

Como 3 no es  cero se devolverá el producto de 3 y el factorial de 2

Ahora , como 2 no es cero se devolverá el producto de 2 y el factorial de 1

Una vez mas, 1 no es cero, se devuelve el producto de 1 y el factorial de 0

Ahora si 0 es 0 y se devuelve 1

Como ya se tiene el factorial de 0 que es 1, se devuelve el producto de 1 y 1=1

Ya se tiene el factorial de 1 que es 1, se devuelve el producto de 2 y 1=2

Ya se tiene el factorial de 2 que es 2, se devuelve el producto de 3 y 2=6

Listo, el factorial de 3, que es seis. Nótese la estructura por niveles de la ejecución, ya que mas adelante se le mencionara en relación al consumo de recursos.

Solución clásica

Ahora se implementara una solución clásica( imperativa,en el que se sigue un flujo o secuencia de operaciones):

function factorial(natural){

resultado=1;

for(i=1;i<=natural;i++){

resultado*=natural;

}

return resultado;

}

En primer lugar, esta definición usa mas espacio que la recursiva y no se puede reducir a un renglón. Ademas obliga a almacenar un estado y al usar un ciclo for nos hace delimitarlo. Hay que permitir que i llegue a ser igual a natural o solo a un numero menor? Esto suele ser fuente de errores en problemas mas complejos.

En principio puede parecer mas natural y sencillo usar esta implementación, pero no hay que dejarse engañar, eso probablemente sea debido a que es el paradigma que hemos aprendido y usado siempre. El observador atento habrá notado que en la solución recursiva de factorial solo hay que pensar en dos cosas, y ese análisis se cumple para todo algoritmo recursivo.

Estructura de un algoritmo recursivo

Todo algoritmo recursivo cuenta con dos partes: El caso base y la llamada recursiva.

Caso base

El caso base es fundamental ya que sin el la recursión continuaría hasta el infinito, causando un desbordamiento de la memoria. Siempre debe escribirse una expresión condicional para revisar si se ha llegado al caso base o no y devolver el resultado adecuado. En el ejemplo del factorial el caso base sucede cuando el parametro natural es 0. Cabe mencionar que también podría escogerse el 1 como caso base para ahorrar pasos en la ejecución ya que su factorial también es 1 pero estrictamente hablando la definición no seria completa para los naturales.

Llamada recursiva

Si no se cumple la condición del caso base debe ejecutarse la llamada recursiva. No hay que olvidar actualizar los argumentos de la llamada  a un estado mas simple que se acerque al caso base, de lo contrario también se corre el riesgo de desbordar la memoria.

Próximo numero

Hasta aquí la introducción a la programación recursiva. En el siguiente numero se exploraran otros problemas y conceptos relacionados con la eficiencia  y optimizacion de los algoritmos.

Advertisements
Jugando con la recursion 1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s