Recursión

De Departamento de Informatica
Saltar a: navegación, buscar

¿Qué es la Recursión?

La recursión en sí, es la definición de un proceso en base a sí mismo, en programación hace referencia a la forma de resolver el problema de la implementación de algunos tipos de funciones. Esto se logra haciendo que la funcin en cuestión se llame a sí misma, para poder reducir el problema hasta llegar a un caso base.

Para poder crear una función recursiva se deben tener en cuenta algunas cosas antes, para ejemplificar esto mejor, utilizaremos el clásico ejemplo del factorial.

El factorial se define de la siguiente forma:

n! = n * (n – 1)!

y además, se tiene que:

0! = 1

Lo primero que se debe pensar al crear una función recursiva, es el caso base, el cual determinará el fin de las llamadas recursivas de la función. Aplicandolo a nuestro ejemplo, esto no es nada mas que el factorial de cero (0! = 1).

Luego, de no cumplirse nuestro caso base, se procede a la llamada recursiva. Esto en C se realiza de la siguiente manera:


int factorial(int numero)
{ 
    if ( numero == 0)
        return 1;
    else
        return numero * factorial(n-1); /* Esto equivale a que n! = n * (n-1)! */
}


Como se ve, se están aplicando las definiciones de factorial anteriormente dadas 0! = 1 y n! = n * (n − 1)!).

Gráficamente, esto se puede visualizar asi:

Recursion factorial.gif

Como se aprecia en la imagen, la llamada recursiva se detiene cuando el número sea 0. En ese caso, se retorna 1 (factorial de 0) y comienza a devolverse “hacia atrás”, retornando las multiplicaciones correspondientes.

Es de suma importancia que al crear funciones recursivas, tener un caso base bien determinado, pues la recursion consume recursos y una funciones recursivas mal hechas, podrían llamarse infinitas veces y colapsar el programa.

Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas