Recursividad

Primero consideraremos a la recursividad de manera conceptual, luego, examinaremos dos programas que contienen funciones recursivas. Los métodos para solucionar problemas recursivos tienen un conjunto de elementos en común, se llama a una función recursiva para resolver un problema. En realidad la función sólo sabe cómo resolver el(los) caso(s) más sencillo(s), o lo que se conoce como base(s). Si a la función se le llama con el caso base, la función sencillamente devuelve el resultado. Si a la función se le llama con un problema más complicado, la función divide el problema en  partes conceptuales, la parte que la función sabe cómo resolver y la parte que la función o resolver. Para hacer que la recursividad sea factible, la segunda parte debe replantear original, pero debe ser una versión ligeramente más sencilla, o más pequeña, que la version original  del problema. Este nuevo problema se parece al problema original, de manera que se lanza (se llama) a una copia nueva de sí misma para trabajar en el problema más pequeño; a esto se le llama llamada recursiva o también paso recursivo. A menudo, el paso recursivo incluye la pa­rvada return, debido a que su resultado se combinará con la parte del problema que la sabe  cómo resolver para formar un resultado que se transmitirá hacia la llamada original, posiblemente en el main.

 

Los lenguajes de programación que apoyan la programación estructurada y/o la programación orientada a objetos permiten la recursividad. Existen cientos de estos lenguajes, algunos de ellos:

1. C
2. C++
3. Java
4. Pascal
5. Object Pascal
6. C#
7. Visual Basic
8. J#
9. Perl
10. Visual FoxPro (con limitaciones)
11. JavaScript (tiene errores de implementación con respecto a la recursividad).
12. PHP

La recursividad y la iteración (ejecución en bucle) están muy relacionadas, cualquier acción que pueda realizarse con la recursividad puede realizarse con iteración y viceversa. Normalmente, un cálculo determinado se prestará a una técnica u otra, sólo necesita elegir el enfoque más natural o con el que se sienta más cómodo.

Una aproximación diferente a la programación de una función que calcule el factorial de un número estaría basada en el siguiente razonamiento:

 

 

Siendo el codigo en programación de la siguiente manera:

 

long Factorial(int n)

{

   if (n == 0)

     return 1;

   else

   return (n * Factorial (n - 1)); //aqui se esta llamando asi misma aqui                     //ocurre la recursividad

}

 

otros ejemplo es el problema de las ocho reinas:

 

El problema de las ocho reinas y en general de las N reinas, se basa en colocar 8 reinas en un tablero de 8´ 8 (o N en un tablero de NxN, si el problema se generaliza), de forma que en no puede haber dos piezas en la misma línea horizontal, vertical o diagonal, ver Figura 1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

el codigo es:

 

#include <stdio.h>

#define N 8

#define n (N+1)

#define True 1

#define False 0

 

void EnsayaReina(int i, int* solucion);

void EscribeSolucion();

void Inicializa();

void Anota(int i, int j) ;

void BorraAnotacion(int i, int j);

int Reinas[n];

int DiagPrin[2 * N], DiagSec[2 * N],Col[n];

 

void Inicializa()

{

 int i;

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

   {

       Col[i] = True;

       Reinas[i] = 0;

    }

 for(i =1 ;i < 2 * N; i++)

   {

        DiagSec[i] = True;

        DiagPrin[i] = True;

   }

}

 

void Anota(int i, int j)

{

     Col[j]=False;

     DiagPrin[i – j + N] = False;

     DiagSec[ i + j - 1] = False;

     Reinas[i] = j;

}

 

void BorraAnotacion(int i, int j)

{

     Col[j]=True;

     Reinas[i]=0;

     DiagPrin[i – j + N] = True; 

     DiagSec[i + j - 1] = True;

}

 

int Aceptable( int i, int j)

{

     return (Col[j] && DiagPrin[i – j + N] && DiagSec[ i + j - 1]);

}

 

void EnsayaReina(int i, int* solucion)

{

    // esquema recursivo de una solución

   int j = 0;                                      /* inicializar posibles movimientos */

   do {

     j++;                                   /* tentativa de colocar reina i en fila j */

       if (Aceptable(i,j))

      {

        Anota(i,j) ;

         if (i < N)

             EnsayaReina(i+1,solucion);

        else                                             /* todas las reinas colocadas */

           *solucion = True;

        if (!(*solucion))

        BorraAnotacion(i,j);

      }

   } while(!(*solucion) && (j < N));

}

 

void EscribeSolucion()

{ 

  int i;

   puts("\n Número de columna se colocan cada reina\n");

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

     printf("\t Reina %d  en columna %d \n",i,Reinas[i]);

}

 

void main(void)

{ 

   int TieneSolucion;

   TieneSolucion = False;

   Inicializa();

   EnsayaReina(1,&TieneSolucion);

   if (TieneSolucion)

   EscribeSolucion();

}

 

 

 

 

Conclusión.

 

 

Se puede decir que la recursividad es una técnica de programación bastante útil y muy interesante de estudiar. A través de los ejemplos que el individuo pueda revisar, aprenderá con más rapidez y sencillez lo que es programar recursivamente e incluir esta técnica cuando se le presente un problema como los que fueron mencionados anteriormente. La asignación de memoria, sea estática o dinámica, en realidad se tendrá que aplicar en cualquier programa al momento de su codificación; tomando en cuenta que cada programador tiene su estilo de programar. El ejemplo de las torres de Hanoi tanto como el ejemplo de las ocho reinas son problemas claves que tienen que ver directamente con lo que es la recursividad.