Definición de Función recursiva

Anuncios

Tipo de función de programación más compleja. Una función común es llamada desde otra función; pero es posible crear funciones que puedan llamarse a sí mismas, las funciones recursivas.

Una función puede ser recursiva tanto de forma directa (si es llamada a sí misma) o de forma indirecta (si llama a una función que luego la llama).

Existen algunos problemas que pueden ser resueltos de forma más eficiente (o su resolución puede ser más naturalmente pensada) utilizando funciones recursivas.

Una función recursiva puede dar origen a un típico problema en programación, la recursión infinita (bucle infinito), que es cuando una función se llama a sí misma infinitas veces. Esto detiene el normal funcionamiento de un programa.

Para que esto no suceda una función recursiva debe ser muy bien pensada. Principalmente una función recursiva debe saber resolver el caso más simple, llamado caso base. Si la función es llamada con el caso base, inmediatamente retorna el resultado (no necesita volver a llamarse a sí misma para poder resolverlo).

Si la función es llamada con un caso más complejo, las sucesivas llamadas a sí mismas irán virtualmente descomponiendo ese caso hasta llegar a un caso base, para luego determinar el resultado final de la función. Para entender mejor el concepto de función recursiva expondremos un caso sencillo: cálculo del factorial de un número.

El factorial de un número es una función matemática que tiene la siguiente fórmula:
n! = n * (n – 1)!

O sea, el factorial (simbolizado con un signo de exclamación) de un número n resulta de multiplicar el mismo número por el factorial de ese número menos uno. De esta manera se va restando hasta llegar al caso base que es el factorial de 1 y su resultado es 1. Por ejemplo, el factorial de 5 es: 5! = 5 * 4!
el factorial de 4 es: 4! = 4 * 3!
el factorial de 3 es: 3! = 3 * 2!
el factorial de 2 es: 2! = 2 * 1!
el factorial de 1 es: 1! = 1
Como se ve, el factorial de uno es el caso base (el caso más simple conocido).

En definitiva, el factorial de 5 es: 5! = 5 * 4 * 3 * 2 * 1

El cálculo de factorial es posible hacerlo tanto con una estructura de control como usando una función recursiva. El código de la función recursiva puede ser:

int factorial(int numero)
{
if (numero == 1)
return 1;
else

return (numero * factorial(numero – 1));
}

Por ejemplo, al llamar a la función de la siguiente forma: factorial(5), lo que hará es verificar si el número pasado es el caso base (o sea, si es 1). Si es así, retorna el resultado, o sea, 1. En el caso de que el número no sea 1, devuelve el resultado de multiplicar ese número por la llamada a factorial (a sí misma) con número restado en 1.

Se iniciará la ejecución de la función pero esta vez con el número 4. Este proceso se repetirá tantas veces como sea necesario hasta que la variable numero sea el caso base, o sea 1. Una vez que se llega al caso base, comienza a calcular el factorial (de atrás hacia adelante).