Recursividad

Centro de Enseñanza

Técnica Industrial

a) Investigación:

La recursividad es una técnica de programación que nos permite que un bloque de instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas.

Una función recursiva es aquella que se llama a si misma para resolverse. Dicho de otra manera, una función recursiva se resuelve con una llamada a si misma, cambiando el valor de un parámetro en la llamada a la función. A través de las sucesivas llamadas recursivas a la función se van obteniendo valores que, computados, sirven para obtener el valor de la función llamada originalmente.

El proceso de llamadas recursivas siempre tiene que acabar en una llamada a la función que se resuelve de manera directa, sin necesidad de invocar de nuevo la función. Esto será siempre necesario, para que llegue un momento que se corten las llamadas reiterativas a la función y no se entre en un bucle infinito de invocaciones.

Por ejemplo, factorial de 4 es igual a 4 * 3 * 2 * 1. Si nos fijamos, para el ejemplo de factorial de 4 (factorial se expresa matemáticamente con un signo de admiración hacia abajo, como 4!), se puede resolver como 4 * 3! (4 * factorial de 3). Es decir, podemos calcular el factorial de un número multiplicando ese número por factorial de ese número menos 1.

function factorial(n){

if(n==1)

return 1

else

return n * factorial(n-1)

}

Como definición general, podemos decir que una función recursiva es aquella que se llama a si misma para resolverse. Dicho de otra manera, una función recursiva se resuelve con una llamada a si misma, cambiando el valor de un parámetro en la llamada a la función. A través de las sucesivas llamadas recursivas a la función se van obteniendo valores que, computados, sirven para obtener el valor de la función llamada originalmente.

El proceso de llamadas recursivas siempre tiene que acabar en una llamada a la función que se resuelve de manera directa, sin necesidad de invocar de nuevo la función. Esto será siempre necesario, para que llegue un momento que se corten las llamadas reiterativas a la función y no se entre en un bucle infinito de invocaciones.

Quizás en la teoría cueste más ver lo que es una función recursiva que por la práctica. Un ejemplo típico de recursividad sería la función factorial. El factorial es una función matemática que se resuelve multiplicando ese número por todos los números naturales que hay entre él y 1.

Por ejemplo, factorial de 4 es igual a 4 * 3 * 2 * 1. Si nos fijamos, para el ejemplo de factorial de 4 (factorial se expresa matemáticamente con un signo de admiración hacia abajo, como 4!), se puede resolver como 4 * 3! (4 * factorial de 3). Es decir, podemos calcular el factorial de un número multiplicando ese número por factorial de ese número menos 1.

n! = n * (n-1)!

En el caso de la función factorial, tenemos el caso básico que factorial de 1 es igual a 1. Así que lo podremos utilizar como punto de ruptura de las llamadas recursivas.

Así pues, vamos a realizar la codificación de la función recursiva factorial. Primero veamos un pseudocódigo:

funcion factorial(n)

si n=1 entonces

factorial = 1

sino

factorial = n * factorial(n-1)

fin funcion

Ahora veamos cómo se implementaría esta función con el lenguaje de programación Javascript:

function factorial(n){

if(n==1)

return 1

else

return n * factorial(n-1)

}

Como se puede ver, la recursividad no representa ninguna dificultad y de hecho es una herramienta muy útil para programación de algoritmos. En desarrollo web .com hemos publicado en diversos lugares funciones que trabajan de forma recursiva. Entiendo que en un principio puede resultar dificil de entender o de saber cuando utilizar, pero cuando dominemos el concepto veremos que es una manera excelente de resolver problemas con cualquier lenguaje de programación.

Hay muchos algoritmos que sólo se resuelven con recursividad, o al menos cuya resolución más directa y elegante está basada en realizar funciones recursivas, que se llamen a si mismas para obtener el resultado final. Por ejemplo el recorrido de diversas estructuras de datos, como las de tipo árbol, siempre se acostumbran a realizar de manera recursiva, para poder estar seguros de que pasamos por todas las ramas del árbol.

Recursividad versus iteración

 Tanto la iteración como la recursividad se basan en una estructura de control: la iteración utiliza una estructura de repetición; la recursividad utiliza una estructura de selección.

 Ambas involucran la repetición a través de llamadas repetidas a la función.

 Ambas involucran una prueba de terminación; la iteración termina cuando la condición de continuación del ciclo falla; la recursividad termina cuando no se reconoce un caso base.

 La recursividad tiene sus inconvenientes. Invoca de manera repetida al mecanismo, y por consecuencia, la sobrecarga de llamadas a la función. Esto puede ser costoso tanto en tiempo de proceso como espacio de memoria.

 Cada llamada recursiva crea una copia de la función (en realidad sólo las variables de la función); esto puede consumir una considerable cantidad

...