RECURSIVIDAD en C

| 2013-04-23 | No hay comentarios »

En C, las funciones pueden llamarse a sí mismas. Si una expresión en el cuerpo de una función llama a la propia función, se dice que ésta es recursiva. La recursividad es el proceso de definir algo en términos de sí mismo y a veces se llama definición circular.

Los ejemplos de recursividad abundan.

Para que en lenguaje de computadora sea recursivo, una función debe ser capaz de llamarse a sí misma. Un sencillo ejemplo es la función fact(), que calcula el factorial de un entero. El factorial de un número N es el producto de todos los número entre 1 y N. Por ejemplo, el factorial de 3 es 1 x 2 x 3, ó 6. a continuación se muestra fact() y su equivalente iterativa en 29FACT.CPP(no encontré)


Long unsigned int fact(int n) /* recursiva */

{

long unsigned int resp;

if(n==1) return(1);

resp = fact(n--)*n;

return (resp);

}

 

long unsigned int factiter(int n);

{

long unsigned int t, resp;

resp=1;

for(t=1; t<n; t++)

resp = resp * t;

return (resp);

}

La versión no recursiva de factiter() debe estar clara. Utiliza un bucle que empieza en 1 y termina en n y que progresivamente multiplica cada número por el producto móvil.

La operación de la recursiva fact() es un poco más compleja. Cuando se llama a fact() con un argumento de 1, la función devuelve 1. En otro caso, devuelve el producto fact(n-1)*n. Para evaluar esta expresión se llama a fact() con n-1. Esto ocurre hasta que n es igual a 1 y las llamadas a la función empiezan a volver.

Al calcular el factorial de 2, la primera llamada a fact() produce una segunda llamada con argumento de 1. Esta llamada devuelve 1, que se multiplica entonces por 2 (el valor original de n). La respuesta, entonces, es 2. (Puede encontrar interesante incluir sentencias cout en fact() para ver el nivel de cada llamada y cuales son las respuestas intermedias.)

Cuando la función se llama a sí misma, se asigna un espacio en la pila para las nuevas variables locales y parámetros, y el código de la función se ejecuta con estas nuevas variables desde el principio. Una llamada recursiva no hace una nueva copia de la función. Sólo son nuevos los argumentos. Al volver de una llamada recursiva se recuperan de la pila las variables locales y los parámetros antiguos, y la ejecución se reanuda en el punto de la llamada a la función dentro de la función. Podría decirse que las funciones recursivas tienen un efecto “telescópico” que las lleva fura y dentro de sí mismas.

La mayoría de las rutinas recursivas no minimizan significativamente el tamaño del código ni ahorran espacio de memoria. Además, las versiones recursivas de la mayoría de las rutinas se ejecutan un poco más despacio que sus versiones iterativas equivalentes, debido a las repetidas llamadas a la función. De hecho, muchas llamadas recursivas a una función pueden hacer que se desborde la pila. Debido a que el almacenamiento de los parámetros de la función y de las variables locales se hace en la pila y cada nueva llamada crea una copia de estas variables, es posible que la pila sobrescriba algún otro dato o la memoria del programa. Sin embargo, lo más probable es que no haya que preocuparse de esto, a menos que una función recursiva pierda el control.

La principal ventaja de las funciones recursivas es que se pueden usar para crear versiones de algoritmo más claras y más sencillas. Por ejemplo, la ordenación rápida (quicksort) es difícil implementar en forma iterativa. Además, algunos problemas, especialmente los problemas relacionados con la inteligencia artificial parece que tienden ellos mismos hacia soluciones recursivas. Por último, algunas personas parece pensar más fácilmente de forma recursiva que de forma iterativa.

Cuando se escriben funciones recursivas, se debe tener una sentencia if en algún sitio que fuerce a la función a volver sin que se ejecute la llamada recursiva. Si no se hace así, la función nunca devolverá el control una vez que se le ha llamado. Es un error muy común el escribir funciones recursivas sin un if.

Acerca del autor: Rodrigo Paszniuk

Ingeniero Informático, amante de la tecnología, la música, el ciclismo y aprender cosas nuevas.

Posts Relacionados

  • Manual intermedio de C++
  • ENTRADAS/SALIDAS STANDARD en C++
  • Manual básico de C++
  • ESTRUCTURAS Y UNIONES en C++



SEGUÍNOS EN FACEBOOK


GITHUB