Recursividad

Un algoritmo se llama recursivo cuando se usa una parte del mismo como solución al problema. El resto es generalmente la solución trivial, o sea aquella cuya solución será siempre conocida, es fácil de calcular o es parte de la definición del problema a resolver. Ésta solución sirve como referencia y permite que el algoritmo tenga una cantidad finita de pasos. Por lo general estos algoritmos se implementan junto a una estructura de datos, la cual es la pila, en la cual se almacenan los resultados parciales de cada recursión.

Para mostrarles un ejemplo de algoritmo recursivo hice este programa que muestra una sucesión de números Fibonacci. Primero veamos la definición:

Los números de Fibonacci se definen como:

F_N = F_N-1 + F_N-2 para N > 2

F₀ = F₁ = 1

que definen la secuencia:

1,1,2,3,5,8,13,21,34,55,89,144, .....

Aquí un programa que hice en C:

#include <stdio.h>

int main(void)
{
    int   num_anterior=0;
    int   num_actual=1;
    int   num_siguiente;
    int cont;
    int x;
   
    printf("Cuantos numeros Fibonacci deseas calcular?\n");
    scanf("%d", &x);
    cont=1;
    system("cls");
    printf("%d\n", num_anterior);
    while (cont<x) {
       
        printf("%d\n", num_actual);
        num_siguiente = num_actual + num_anterior;

        num_anterior = num_actual;
        num_actual = num_siguiente;
        cont++;
    }
    printf("Fin de la sucesion");
    getch();
    return (0);
}

Aquí se aplica la recursividad para calcular el valor siguiente (num_siguiente), pues tiene que recurrir a los valores de num_actual y num_anterior que se sacaron anteriormente para sumarlos. Luego reemplaza num_anterior por num_actual, y num_actual se vuelve el valor anterior de num_siguiente.

Bibliografía

• http://es.wikiversity.org/wiki/Curso_de_Estructuras_de_Datos_y_Algoritmos_/_Algoritmos_recursivos
• www.cs.buap.mx/~titab/files/recursion1.doc