FUNCIONES RECURSIVAS

Las funciones en lenguaje C/C++ pueden ser recursivas, en otras palabras, pueden llamarse a sí mismas directa o indirectamente. La recursividad directa es el proceso mediante el que una función se llama a sí misma desde el propio cuerpo de la función, mientras que la recursividad indirecta implica más de una función.

Un proceso recursivo tiene que tener una condición de finalización, ya que de lo contrario podría continuar infinitamente.

Un ejemplo típico de aplicación de la recursividad es el cálculo del factorial de un número entero. Recordemos que el factorial de un número entero (n!) se calcula de la siguiente manera:    

n! = n * (n-1) * (n-2) * ... * 2 * 1

En principio, la solución a este problema podría realizarse sin tener que utilizar la recursividad con el siguiente programa:

#include <stdio.h>

int factorial(int numero);

main()

{

int valor = 4;

int resultado;

resultado = factorial(valor);

printf("El factorial de %d es %d \n", valor, resultado);

return 0;

}

int factorial(int numero)

{

int i;

int devuelve = 1;

for(i = 1; i <= numero; i++)

{

devuelve = devuelve * i;

}

return devuelve;

          }

Sin embargo, resulta más intuitivo dada la definición de número factorial utilizar una función recursiva como la siguiente:

int factorial(int numero)

{

if(numero == 1)

return 1;

else

return (numero * factorial(numero-1));

}

En la función anterior, en el caso de que el argumento utilizado en la llamada sea 1, ésta devuelve 1, y en caso contrario se calcula un producto que involucra a la variable numero y una nueva llamada a la función cuyo argumento es menor en una unidad (numero -1).

El funcionamiento de una función recursiva se realiza almacenando las llamadas pendientes, con sus argumentos, en la pila en tiempo de ejecución. Veamos un ejemplo: imagina que utilizamos el valor 4 como argumento de la función que calcula el factorial, es decir, factorial(4), el proceso de llamadas será el siguiente:

Llamada # 1:

numero = 4

numero != 1 entonces ejecutamos la siguiente sentencia

return ( 4 * (realizamos la segunda llamada))

Llamada # 2:

numero = 3

numero != 1 entonces ejecutamos la siguiente sentencia

return ( 3 * (realizamos la tercera llamada))

Llamada # 3:

numero = 2

numero != 1 entonces ejecutamos la siguiente sentencia

return ( 2 * (realizamos la cuarta llamada))

Llamada # 4:

numero = 1

numero == 1 entonces se ejecuta la sentencia del if:

return 1

Fin Llamada # 4 -> DEVUELVE 1

return ( 2 * 1)

Fin Llamada # 3 -> DEVUELVE 2

return ( 3 * 2)

Fin Llamada # 2 -> DEVUELVE 6

return ( 4 * 6)

Fin Llamada #1 -> DEVUELVE 24

En la siguiente imagen podemos ver el proceso descrito anteriormente: