Recursividad en Java

¿Qué es la recursividad? El proceso en el que una función se llama a sí misma directa o indirectamente se llama recursividad y la función correspondiente se llama función recursiva. Usando el algoritmo recursivo, ciertos problemas se pueden resolver con bastante facilidad. Ejemplos de tales problemas son Towers of Hanoi (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS of Graph , etc. ¿Cuál es la condición base en la recursividad? En el programa recursivo, se proporciona la solución al caso base y la solución del problema más grande se expresa en términos de problemas más pequeños.

int fact(int n)
{
    if (n < = 1) // base case
        return 1;
    else    
        return n*fact(n-1);    
}

En el ejemplo anterior, se define el caso base para n < = 1 y el valor mayor del número se puede resolver convirtiendo a uno más pequeño hasta alcanzar el caso base. ¿Cómo se resuelve un problema particular usando la recursividad? La idea es representar un problema en términos de uno o más problemas más pequeños y agregar una o más condiciones base que detengan la recursividad. Por ejemplo, calculamos el factorial n si conocemos el factorial de (n-1). El caso base para el factorial sería n = 0. Devolvemos 1 cuando n = 0. ¿Por qué se produce un error de desbordamiento de pila en la recursividad? Si el caso base no se alcanza o no se define, entonces puede surgir el problema de desbordamiento de pila. Tomemos un ejemplo para entender esto.

int fact(int n)
{
    // wrong base case (it may cause
    // stack overflow).
    if (n == 100) 
        return 1;

    else
        return n*fact(n-1);
}

Si se llama fact(10), llamará fact(9), fact(8), fact(7) y así sucesivamente, pero el número nunca llegará a 100. Por lo tanto, no se alcanza el caso base. Si estas funciones agotan la memoria en la pila, se producirá un error de desbordamiento de pila. ¿Cuál es la diferencia entre recursividad directa e indirecta? Una función fun se llama recursiva directa si llama a la misma función fun. Una función fun se llama recursiva indirecta si llama a otra función, digamos fun_new y fun_new llama a fun directa o indirectamente. La diferencia entre la recursividad directa e indirecta se ilustra en la Tabla 1.

• Recurrencia directa:

void directRecFun()
{
    // Some code....

    directRecFun();

    // Some code...
}

• recursividad indirecta:

void indirectRecFun1()
{
    // Some code...

    indirectRecFun2();

    // Some code...
}

void indirectRecFun2()
{
    // Some code...

    indirectRecFun1();

    // Some code...
}

¿Cuál es la diferencia entre la recursividad con cola y sin cola? Una función recursiva es recursiva de cola cuando la llamada recursiva es lo último que ejecuta la función. Consulte el artículo de recursión de cola para obtener más detalles. ¿Cómo se asigna la memoria a diferentes llamadas de función en recursividad?Cuando se llama a cualquier función desde main(), la memoria se le asigna en la pila. Una función recursiva se llama a sí misma, la memoria para la función llamada se asigna encima de la memoria asignada a la función que llama y se crea una copia diferente de las variables locales para cada función llamada. Cuando se alcanza el caso base, la función devuelve su valor a la función que la llamó y la memoria se desasigna y el proceso continúa. Tomemos el ejemplo de cómo funciona la recursión tomando una función simple. 

// A Java program to demonstrate
// working of recursion
 
class GFG {
    static void printFun(int test)
    {
        if (test < 1)
            return;
 
        else {
            System.out.printf("%d ", test);
 
            // Statement 2
            printFun(test - 1);
 
            System.out.printf("%d ", test);
            return;
        }
    }
 
    public static void main(String[] args)
    {
        int test = 3;
        printFun(test);
    }
}

3 2 1 1 2 3 

Cuando se llama a printFun(3) desde main(), la memoria se asigna a printFun(3) y una prueba de variable local se inicializa a 3 y las declaraciones 1 a 4 se colocan en la pila como se muestra en el diagrama a continuación. Primero imprime ‘3’. En la declaración 2, se llama a printFun(2 ) y se asigna memoria a printFun(2) y una prueba de variable local se inicializa a 2 y las declaraciones 1 a 4 se colocan en la pila. De manera similar, printFun(2) llama a printFun(1) y printFun(1) llama a printFun(0) . printFun(0) va a la sentencia if y vuelve a printFun(1) . Declaraciones restantes de printFun(1)se ejecutan y vuelve a printFun(2) y así sucesivamente. En la salida, se imprimen los valores de 3 a 1 y luego se imprimen de 1 a 3. La pila de memoria se muestra en el siguiente diagrama. ¿Cuáles son las desventajas de la programación recursiva sobre la programación iterativa? Tenga en cuenta que tanto los programas recursivos como los iterativos tienen el mismo poder de resolución de problemas, es decir, todos los programas recursivos se pueden escribir de forma iterativa y viceversa. El programa recursivo tiene mayores requisitos de espacio que el programa iterativo ya que todas las funciones permanecerán en la pila hasta que se alcance el caso base. También tiene mayores requisitos de tiempo debido a las llamadas a funciones y la sobrecarga de retorno.

 ¿Cuáles son las ventajas de la programación recursiva sobre la programación iterativa? La recursión proporciona una forma limpia y sencilla de escribir código. Algunos problemas son inherentemente recursivos como recorridos de árboles, Torre de Hanoi , etc. Para tales problemas, se prefiere escribir código recursivo. Podemos escribir dichos códigos también iterativamente con la ayuda de una estructura de datos de pila. Por ejemplo, consulte Recorrido de árbol en orden sin recursividad , Torre iterativa de Hanoi .

El ejemplo clásico de recursividad es el cálculo del factorial de un número.

El factorial de un número N es el producto de todos los números entre 1 y N.

El siguiente código dado calcula el factorial de los números: 3, 4 y 5.

3= 3*2*1 (6)

4= 4*3*2*1 (24)

5= 5*3*2*1 (120)

// A simple example of Recursion
class GFG{
   
// recursive method
int fact(int n){
int result;
   
  if(n==1) return 1;
  result =fact(n-1) *n;
  return result;
}
}
 
 
class Recursion {
   
    public static void main (String[] args) { 
      GFG f= new GFG ();
       
      System.out.println("Factorial of 3 is " + f.fact(3));
      System.out.println("Factorial of 4 is " + f.fact(4));
      System.out.println("Factorial of 5 is " + f.fact(5));
    }
}

Factorial of 3 is 6
Factorial of 4 is 24
Factorial of 5 is 120