Recursividad

Publicado por Mario en

La recursividad es una técnica de programación muy utilizada para resolver problemas con un alto grado de complejidad. Dicha técnica se basa en resolver un problema mediante recursión, es decir, la solución final depende de las soluciones parciales del mismo problema. Algunas técnicas muy utilizadas son las siguientes: “Divide y Vencerás” o “Backtracking” emplean la recursividad como modo de resolución.

En resumen, la mayoría de los lenguajes de programación dan soporte a la recursión, permitiendo a una función llamarse a sí misma mediante el texto del programa. Los ejemplos expuestos, a continuación, han sido codificados en java.

ALGORITMOS RECURSIVOS

Un algoritmo recursivo es un algoritmo que expresa la solución a un problema llamándose a sí mismo.

Generalmente, las primeras llamadas al subprograma son de una complejidad muy grande y el objetivo es ir reduciendo dicha complejidad hasta que se llegue a una solución, para que se pueda manejar iterativamente. Por lo tanto, llegar a este resultado se conoce como caso base.

Para realizar un algoritmo recursivo se debe definir el caso base con su solución, cuando no se pueda resolver mediante el caso base se define la resolución recursiva que tiene como objetivo llegar al caso anterior.

A grandes rasgos el funcionamiento es similar al de una pila:

  • Se crea una pila que contendrá la operación recursiva.
  • Cada nueva llamada apila la nueva solución parcial
  • El fin de cada llamada desapila y recupera el valor de la llamada anterior y así sucesivamente.

EJEMPLOS DE ALGORITMOS RECURSIVOS

  • Suma números pares positivos hasta un número obtenido: el algoritmo suma todos los números pares positivos desde el 0 hasta n.
    public static int suma(int n){
            if(n<=0)
                return n;
            else if(n%2 != 0)
                return suma(n-1);
            else 
                return n+suma(n-1);
        }

    La pila resultante de la operación anterior es la siguiente:

     

    [ suma(0) , 2+suma(1), suma(2), 4+suma(3) ]

    Se puede apreciar cómo se van realizando las diferentes llamadas, dependiendo si el número es par o no. Una vez calculado que el valor de “n” es “0” (Caso base), se procede a desenrollar la pila tomando todas las soluciones parciales, para así llegar a la solución final.

  • Factorial de un número: consiste en multiplicar n por todos los números anteriores a él hasta el 1.
    public static int factorial(int n){
            if(n <= 1)//Caso base
                return n;
            else
                return n*factorial(n-1);
        }

    El caso base es en “1” porque es cuando se puede dar solución al problema tomando las soluciones/medidas parciales con las que se iba reduciendo la complejidad. De este modo, también está contemplado para cuando es menor que “1”, porque en el caso de introducir por ejemplo el “0” se debe devolver el número en cuestión.

  • Exponencial de un número: el exponente de un número consiste en multiplicar ese número consigo mismo las veces que indica un exponente, así con este algoritmo programaremos esa operación de manera recursiva, en el cual “n” representa el número y “e” el exponente.
    public static int exponencial(int n,int e){
            if(e==0)
                return 1;
            else if(e==1)
                return n;
            else
                return n*exponencial(n,e-1);
        }

    En este caso tenemos dos casos base para representar correctamente la solución final. Al igual que en los ejemplos anteriores se parte de un término complejo y se va aminorando hasta llegar al caso base.

En definitiva, este tipo de programación es muy compleja y abstracta y la mejor manera de entenderla y aplicarla es llevándola a la práctica, para que así resulte más fácil realizar dichos procedimientos.

 

 


Deja un comentario