Recursividad en programación

Publicado el 23 de enero de 2008

La recursividad, es un concepto bastante importante y bien básico de la programación. Sin embargo es bastante difícil de asimilar al principio. Se supone que es algo que se va entendiendo con práctica y tiempo.

La mejor definición sin duda de la recursión, es la encontrada en el diccionario hacker:

recursión
-ver recursión.

Por ejemplo GNU, es un acrónimo recursivo (GNU’s Not Unix), ya que la G en GNU, significa GNU, cuya G significa GNU, y así recursivamente…
Pensar de forma recursiva es complicado, y no es un proceso intuitivo.

En programación, una función es recursiva cuando se llama a sí misma. A continuación un ejemplo para intentar entender recursividad. A mí me viene bien para practicarlo para mi examen de algoritmos en marzo. Espero que quede entendible!

Uno de los ejemplos más clásicos es el factorial de un número. Intenta seguir la explicación razonando cada paso. Para cualquier entero positivo N, el factorial de N (que se expresa como N!) es el producto (multiplicación) de todos los enteros menor a él:

  • 1! = 1
  • 2! = 1 x 2 = 2
  • 3! = 1 x 2 x 3 = 6
  • 4! = 1 x 2 x 3 x 4 = 24
  • 5! = 1 x 2 x 3 x 4 x 5 = 120
  • 6! = 1 x 2 x 3 x 4 x 5 x 6 = 720

Ahora, repasando atentamente, se puede ver que el factorial de cada número incluye el factorial de todos los números anteriores a él. Lo escrito en corchetes rectos a continuación es una referencia, no a nivel matemático:
“2!” es “1[1!] x 2″
“3!” es “(1 x 2)[2!] x 3″
Y así sucesivamente. Para cualquier entero N mayor a 1, podemos decir que el factorial de N es igual al factorial del número anterior a N multiplicado por N. La fórmula N! = (N-1)! x N. Vuelve a la lista de factoriales de 1 a 6. Busca en cada caso los términos que son factorial del número anterior para darte cuenta. Entonces se podria decir que una buena practica es encontrar el factor en el resultado que se repite.
Pasando ésto a función en C, podemos hacer una función a la que le pasamos un número, y nos devuelve el factorial:

int factorial(int n){
return n * factorial(n - 1);
}

Ahí tenemos nuestra primera función recursiva. Pero si compilamos el código y ejecutamos el programita, obtenemos una hermosa violación de segmento.

El problema es que la función definida arriba no termina nunca, va a seguir restándole 1 a N por siempre. Siempre vamos a poder restarle 1 a cualquier n, por lo que la función va a seguir ejecutándose a sí misma por siempre. Además, para cualquier número positivo, factorial de n va a devolver 0, porque cualquier multiplicación con 0 como término devuelve 0. Y restarle 1 recursivamente a cualquier entero positivo, eventualmente dará cero.
Para que la función recursiva esté completa, además de llamarse a sí misma, necesita una forma de finalizar, una condición.
Por definición, el factorial de 1 es 1 (1!=1) así como el factorial de 0 (0!=1)también es 1. Por lo que podemos implementar ésta condición para que la función no sea interminable.
Así, la definición de la función consta de la recursiva que se llama a sí misma, y la condición para detenerse.

int factorial(int n){
     if n==1{
          return 1;
     }else{
          return n * factorial(n-1);
     }
}

O con un while:

int factorial(int n){
     while (n!=1){
          return n * factorial(n-1);
     }
     return 1;
}

Y bueno, eso es mi primer intento por explicar qué es la recursividad en la programación y cómo funciona con un ejemplo. Otro buen ejemplo es la serie de Fibonacci, pero ésta da para un estudio más a fondo, ya que tiene bastantes cosas interesantes. También es interesante la Torre de Hanoi, resulta bastante interesante y clásico a la hora de aplicar recursividad.

Tengo un par de problemitas de Martin Gardner en los que se me ocurre aplicar también una función recursiva, veré qué pasa. Como en posts anteriores con éste tipo de planteos teóricos, cualquier crítica, corrección, consulta, opinión, etc. es bienvenida en los comentarios o a través del formulario de contacto de la web. Uso éste tipo de posts no solo para compartir conocimientos sino para aprender más.

A continuación el código fuente de un programita que recibe un número como parámetro, y devuelve el factorial. Sé que funciona hasta el número 12, después empieza a dar resultados raros. Supongo que por la limitación del tipo de datos, pero puede haber algún error más importante del que yo no me dé cuenta en éste momento, se agradecen correcciones:

32px-nuvola_mimetypes_source_c.pngfactorial.c

Éste artículo fue actualizado en:
Aprendiendo programación: recursividad 2ª parte

15 comentarios en este post

Feed de comentarios
  1. Avatar

    Leandro 23 enero. 2008 - 15:50

    Te anda hasta doce por la limitación del printf %d muestra integers.
    Además el cabezal debería ser:
    unsigned long factorial(unsigned long n)
    Lo otro que no entiendo es el while n=!1, si bien anda creo que es más prolijo como la instrucción siguiente se va a ejecutar una única vez (el return), hacerlo con el if n!=1
    Y lo último es que 0! está definido 0!=1

    Firefox 2.0.0.11 Windows XP
  2. Avatar

    GarbGe 23 enero. 2008 - 15:52

    hace tiempo que no leia el blog, y ahora que veo algo de lo que se no puede dejar de aportar =)
    ahora los consejos:
    ·veo que usaste la funcion atoi, lo que significa que estas trabajando con cadenas(string), yo te recomendaria que solo utilisaras int, nunca trabajo con cadenas mientras no sea necesario ;P
    ·
    mi prog =) esta en c++ pero la idea es la misma

    #include
    using namespace std;
    int recu(int num)
    {
    if(num == 0 || num == 1)
    {
    return 1;
    }
    else
    {
    return num* recu(num -1);
    }
    }
    int main()
    {
    int num;
    cout <> num;

    cout <<“El factorial es:”<<recu(num)<<endl;
    }

    ahora que he vuelto a casa, dare mas vueltas por aca xD
    S A L U 2

    Firefox 2.0.0.11 Windows XP
  3. Avatar

    Mauricio 23 enero. 2008 - 16:14

    Para mi el error estuvo en la oración “Pasando ésto a función en C…”, deberías haber dicho pseudo-código.
    Son buenos los aportes para aprender un poco de C, aunque creo que la idea era sólo dar un ejemplo sencillo de lo que es recursividad.

    Saludos.

    Firefox 2.0.0.11 Ubuntu
  4. Avatar

    Cristian 5 octubre. 2008 - 01:26

    Gracias por poner esto, me ha sido de grán ayuda para entender recursividad.

    El código de arriba tiene un error eso si. Al intentar calcular el factorial de 0, la condición que lo detiene debería ser:

    int factorial(int n){
         if n==0{
              return 1;
         }else{
              return n * factorial(n-1);
         }
    }

    Salu2 🙂

    Internet Explorer 7.0 Windows XP
  5. Avatar

    Frank 14 marzo. 2011 - 07:00

    Se requiere hacer que la funcion factorial no acepte enteros negativos, estas funciones regresan el factorial de -1, -2, -3, etc… lo que esta mal por que no existe factorial de numeros negativos, requieren un
    if (n < 0) return 0;

    Saludos!

    Internet Explorer 8.0 Windows Vista
  6. Avatar

    Roy 15 mayo. 2014 - 18:11

    Tengo una inquietud cuando defines el factorial:
    “El factorial de N (que se expresa como N!) es el producto (multiplicación) de todos los
    enteros menor a él”
    Según eso el factorial 4 seria:
    4! = 1*2*3 = 6
    ya que 4 no es menor que 4, ademas todos los números menores de N incluyen negativos en este caso,
    Esta es la definición que considero acorde(la de wikipedia):
    “El factorial de N se define como el producto de todos los números enteros positivos desde 1 hasta N”

    Google Chrome 34.0.1847.137 Mac OS
  1. WordPress Recursividad | 4 bits blog | 4 abril. 2008 - 11:07

    […] Tenéis más información en este post de Picando Código. […]

  2. WordPress Frase del día: Recursividad | Picando Código | 28 octubre. 2008 - 12:19

    […] ¿Qué es recursividad? […]

Dejar un comentario

Notificarme los nuevos comentarios por correo electrónico. Tambien puedes suscribirte sin comentar.

Toasty!