Java Language
Recursion

Introducción

Observaciones

La idea básica de la recursión.

¿Qué es la recursión?

En general, la recursión es cuando una función se invoca a sí misma, ya sea directa o indirectamente. Por ejemplo:

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

Condiciones para aplicar la recursividad a un problema:

Hay dos condiciones previas para usar funciones recursivas para resolver un problema específico:

1. Debe haber una condición base para el problema, que será el punto final de la recursión. Cuando una función recursiva alcanza la condición base, no hace más llamadas recursivas (más profundas).

2. Cada nivel de recursión debería estar intentando un problema más pequeño. La función recursiva divide el problema en partes cada vez más pequeñas. Suponiendo que el problema es finito, esto asegurará que la recursión termine.

En Java hay una tercera condición previa: no debería ser necesario repetir demasiado para resolver el problema; Ver recursión profunda es problemática en Java

Ejemplo

La siguiente función calcula los factoriales utilizando la recursividad. Observe cómo el método factorial llama a sí mismo dentro de la función. Cada vez que se llama a sí mismo, reduce el parámetro n en 1. Cuando n alcanza 1 (la condición base), la función no retrocederá más.

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{Esta no es una forma práctica de calcular factoriales en Java, ya que no tiene en cuenta el desbordamiento de enteros o el desbordamiento de la pila de llamadas (es decir, las excepciones de StackOverflowError ) para valores grandes de n .}

Cálculo del Número N. de Fibonacci

El siguiente método calcula el número Nth Fibonacci usando la recursión.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

El método implementa un caso base (n <= 2) y un caso recursivo (n> 2). Esto ilustra el uso de la recursión para calcular una relación recursiva.

Sin embargo, aunque este ejemplo es ilustrativo, también es ineficiente: cada instancia individual del método llamará a la función en sí misma dos veces, lo que llevará a un crecimiento exponencial en el número de veces que se llama a la función a medida que N aumenta. La función anterior es O (2 ^N ), pero una solución iterativa equivalente tiene complejidad O (N). Además, hay una expresión de "forma cerrada" que se puede evaluar en multiplicaciones de punto flotante O (N).

Cálculo de la suma de enteros de 1 a N

El siguiente método calcula la suma de enteros de 0 a N usando la recursión.

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

Este método es O (N) y se puede reducir a un simple bucle usando la optimización de la llamada de cola. De hecho, hay una expresión de forma cerrada que calcula la suma en operaciones O(1) .

Cálculo de la enésima potencia de un número

El siguiente método calcula el valor de num elevado a la potencia de exp mediante recursión:

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

Esto ilustra los principios mencionados anteriormente: el método recursivo implementa un caso base (dos casos, n = 0 y n = 1) que termina la recursión, y un caso recursivo que llama al método nuevamente. Este método es O (N) y se puede reducir a un simple bucle usando la optimización de la llamada de cola.

Invertir una cadena usando Recursión

A continuación se muestra un código recursivo para revertir una cadena

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

    public static String reverse(String s) {
        if (s.length() == 1) {
            return s;
        }
    
        return reverse(s.substring(1)) + s.charAt(0);
    }
}

Atravesando una estructura de datos de árbol con recursión

Considere la clase de nodo con 3 datos de miembros, puntero izquierdo izquierdo y puntero secundario derecho, como se muestra a continuación.

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

Podemos atravesar el árbol construido conectando el objeto de varias clases de Nodos como a continuación, el recorrido se denomina recorrido transversal del árbol.

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

Como se demostró anteriormente, utilizando la recursión podemos atravesar la estructura de datos del árbol sin usar ninguna otra estructura de datos que no sea posible con el enfoque iterativo .

Tipos de recursion

La recursión se puede clasificar como Recursión de cabeza o Recursión de cola , dependiendo de dónde se coloca la llamada de método recursivo.

En la recursión de la cabeza , la llamada recursiva, cuando ocurre, se produce antes que otro procesamiento en la función (piense que sucede en la parte superior, o cabeza, de la función).

En la recursión de cola , es lo contrario: el procesamiento se produce antes de la llamada recursiva. La elección entre los dos estilos recursivos puede parecer arbitraria, pero la elección puede hacer toda la diferencia.

Una función con una ruta con una sola llamada recursiva al comienzo de la ruta usa lo que se llama recursión de cabeza. La función factorial de una exposición anterior utiliza la recursión de la cabeza. Lo primero que hace una vez que determina que se necesita recursión es llamarse a sí mismo con el parámetro decrementado. Una función con una sola llamada recursiva al final de una ruta está utilizando la recursión de cola.

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

Si la llamada recursiva se produce al final de un método, se denomina tail recursion . La recursión de la cola es similar to a loop . El method executes all the statements before jumping into the next recursive call .

Si la llamada recursiva se produce al beginning of a method, it is called a head recursion . El method saves the state before jumping into the next recursive call .

Referencia: La diferencia entre recursión de cabeza y cola.

StackOverflowError & recursion to loop

Si una llamada recursiva es "demasiado profunda", esto se traduce en un StackOverflowError . Java asigna un nuevo marco para cada llamada de método en la pila de su hilo. Sin embargo, el espacio de la pila de cada hilo es limitado. Demasiados fotogramas en la pila llevan al desbordamiento de pila (SO).

Ejemplo

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

Si se llama a este método con parámetros grandes (p. Ej., La recursion(50000) probablemente provocará un desbordamiento de pila. El valor exacto depende del tamaño de la pila de hilos, que a su vez depende de la construcción del hilo, los parámetros de la línea de comandos como -Xss , o el tamaño por defecto para la JVM.

Solución

Una recursión se puede convertir en un bucle almacenando los datos para cada llamada recursiva en una estructura de datos. Esta estructura de datos se puede almacenar en el montón en lugar de en la pila de hilos.

En general, los datos necesarios para restaurar el estado de invocación de un método se pueden almacenar en una pila y un bucle while se puede usar para "simular" las llamadas recursivas. Los datos que pueden requerirse incluyen:

• el objeto para el que se solicitó el método (solo métodos de instancia)
• los parámetros del método
• variables locales
• La posición actual en la ejecución o el método.

Ejemplo

La siguiente clase permite la impresión recursiva de una estructura de árbol hasta una profundidad específica.

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

p.ej

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

Huellas dactilares

(((...)20(...))10((...)30))

Esto podría ser convertido al siguiente bucle:

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}

List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

Nota: Este es solo un ejemplo del enfoque general. A menudo, puede encontrar una forma mucho mejor de representar un marco y / o almacenar los datos del marco.

La recursión profunda es problemática en Java

Considere el siguiente método ingenuo para sumar dos números positivos usando la recursión:

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

Esto es algorítmicamente correcto, pero tiene un problema importante. Si llama a add con una gran a , se bloqueará con un StackOverflowError , en cualquier versión de Java hasta (al menos) Java 9.

En un lenguaje de programación funcional típico (y muchos otros lenguajes) el compilador optimiza la recursión de la cola . El compilador notaría que la llamada a add (en la línea marcada) es una llamada de cola y reescribiría la recursión como un bucle. Esta transformación se llama eliminación de cola.

Sin embargo, los compiladores de Java de la generación actual no realizan la eliminación de la llamada de cola. (Esto no es un descuido simple. Hay razones técnicas sustanciales para esto; vea más abajo). En su lugar, cada llamada recursiva de add hace que se asigne un nuevo marco en la pila del hilo. Por ejemplo, si llama a add(1000, 1) , tomará 1000 llamadas recursivas para llegar a la respuesta 1001 .

El problema es que el tamaño de la pila de hilos de Java se fija cuando se crea el hilo. (Esto incluye el hilo "principal" en un programa de un solo hilo.) Si se asignan demasiados marcos de pila, la pila se desbordará. La JVM detectará esto y lanzará un StackOverflowError .

Un enfoque para lidiar con esto es simplemente usar una pila más grande. Hay opciones de JVM que controlan el tamaño predeterminado de una pila, y también puede especificar el tamaño de la pila como un parámetro del constructor Thread . Desafortunadamente, esto solo "quita" el desbordamiento de pila. Si necesita realizar un cálculo que requiera una pila aún mayor, entonces StackOverflowError regresa.

La solución real es identificar algoritmos recursivos donde es probable una recursión profunda y realizar manualmente la optimización de la llamada de cola en el nivel del código fuente. Por ejemplo, nuestro método de add se puede reescribir de la siguiente manera:

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

(Obviamente, hay mejores maneras de agregar dos enteros. Lo anterior es simplemente para ilustrar el efecto de la eliminación manual de la llamada de la cola).

Por qué la eliminación de la llamada de cola no está implementada en Java (todavía)

Hay varias razones por las que agregar la eliminación de la llamada de cola a Java no es fácil. Por ejemplo:

• Algunos códigos podrían depender de StackOverflowError para (por ejemplo) colocar un límite en el tamaño de un problema computacional.
• Los administradores de seguridad de Sandbox a menudo se basan en analizar la pila de llamadas al decidir si permiten que un código sin privilegios realice una acción privilegiada.

Como John Rose explica en "Llamadas de cola en la máquina virtual" :

"Los efectos de eliminar el marco de la pila de la persona que llama son visibles para algunas API, en particular las verificaciones de control de acceso y el seguimiento de la pila. Es como si la persona que llamó hubiera llamado directamente a la persona llamada. Cualquier privilegio que posea la persona que llama se descarta después de que el control se transfiere al Sin embargo, la vinculación y la accesibilidad del método se calculan antes de la transferencia de control, y tienen en cuenta al llamante que llama ".

En otras palabras, la eliminación de la llamada de cola podría hacer que un método de control de acceso piense erróneamente que un código de confianza estaba llamando a una API sensible a la seguridad.