Entendiendo la Recursividad

 

Todos los que hemos programado con algun lenguaje de programacion sabemos lo dificil que “fue” o “es” comprender al 100% la recursividad. Asi que en este Articulo trataremos de explicarla de forma simple y detallada, al final veremos algun ejemplo pero lo que importa aqui sera la explicacion para que todos sepan como funciona, cuando implementarla y desarrollar tus propias ideas sobre el tema.

La Recursividad se utiliza en programacion y se define en terminos tecnicos como “la forma en la cual se especifica un proceso basado en su propia definicion”, pero vamos a entender primero esto. La recursividad se aplica en una funcion en la que queremos resolver un problema determinado a la que se denomina funcion recursiva, esta funcion solo sabe resolver un caso base, si no recibe en sus parametros ese caso base entonces descompone el problema en uno mas pequeño hasta llegar a ese caso base que la funcion puede resolver.

 

La recursividad en ocaciones puede parecer un proceso infinito o interminable, esto es porque no se entiende por completo como funciona la recursividad, en ocaciones muchos de los problemas de los recien iniciados en la recursividad es olvidar poner un caso base.

 

Los puntos claves para desarrollar una funcion recursiva son:

• Cada llamada recursiva (a la misma funcion) debe definir un problema de menor complejidad
• Debe existir por lo menos un caso base (o sera infinita!)

 

El proceso de la recursividad en resumen es el siguiente:

• Se llama a una funcion recursiva y se le envia un problema
• La funcion analiza si puede resolver el problema (caso base), si es asi lo resuelve y termina
• Sino puede resolver el problema lo convierte en uno de menor complejidad y lo envia de nuevo a otra instancia de su funcion
• El proceso se repite hasta que llega a un caso base que puede resolver, lo resuelve y termina

 

Porque se utiliza la recursividad?
Aunque a algunos suene dificil de creer, existen algunos problemas en programacion los cuales son mas faciles de resolver mediante funciones recursivas, ademas el codigo recursivo es extremadamente simple y legible a la vista.

 

Recursividad VS Iteracion
La mayoria de las veces la recursividad requiere mas tiempo de ejecucion y recursos del sistema para resolver el problema que una misma version Iterativa por lo que la recursividad se utiliza en problemas complejos cuya solucion recursiva es mas facil de obtener, es mas estructurada y mas sencilla de dar mantenimiento.

 

Ejemplo de Recursividad – Calculo de la suma de valores de la serie Fibonacci – En Java
Nota: La serie fibonacci es una serie de numeros hasta llegar a un valor n, donde la serie se comienza con 0,1 y apartir de esos el siguiente valor es la suma de los 2 numeros anteriores.

El Ejemplo en java calcula la serie Fibonacci de forma recursiva y de forma iterativa para que veas las diferencias, ademas medimos el tiempo de ejecucion de ambas funciones.

 

public class Main {
    public static void main(String args[]){
        long t1,t2;
        int val = 20;

        t1 = System.currentTimeMillis();
        System.out.println("Suma de Valores de la Serie Fibonacci Normal de "+val+":n"+fibonacciN(val));
        t2 = System.currentTimeMillis();
        System.out.println("Tiempo Transcurrido: "+(t2-t1)+" milisegundos");

        t1 = System.currentTimeMillis();
        System.out.println("Suma de Valores de la Serie Fibonacci Recursiva de "+val+":n"+fibonacciR(val));
        t2 = System.currentTimeMillis();
        System.out.println("Tiempo Transcurrido: "+(t2-t1)+" milisegundos");

        }

    //Funcion Recursiva
    public static int fibonacciR(int n){
        if(n == 0)
            return 0;
        else if(n == 1)
            return 1;
        else
            return fibonacciR(n - 1) + fibonacciR(n - 2);
    }

    //Funcion Normal
    public static int fibonacciN(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        int temp1=1, temp2=1, f=1;
        for(int i= 3; i < = n; i++){
            f = temp1 + temp2;
            temp1 = temp2;
            temp2 = f;

        }
        return f;
    }
}

 

 

 

Dudas o Comentarios?