arboles

Recursión

Alguna vez hemos visto ese conjunto de muñecos de madera de origen ruso (matrioshkas) en la que uno se encuentra dentro de otro. Dentro del primer muñeco, se encuentra un muñeco menor, ydentro de ese muñeco, hay otro muñeco de menor tamaño y así sucesivamente. Un método recursivo es como los muñecos rusos: se reproducen a sí mismo con versiones más y más pequeñas.



Recursiónes la capacidad de un método o función de invocarse a sí mismo para resolver un problema. Cada vez que un método se llama a sí mismo, se envía una parte más pequeña del problema, a fin de encontraruna solución a la misma.

En Java, un método puede llamar a otros métodos, pero además, ¡se puede llamar a sí mismo! Haciendo una llamada recursiva.

La recursión se forma de dos elementos:

-Caso base. El momento en que se detiene la recursión
- Llamada recursiva. Invocación del método a sí mismo

Cuando se alcanza el caso base, la recursión comienza un proceso llamado “backtracking”(retroceso), resolviendo las llamadas anteriores de sí mismo.

Ejemplo clásico de recursión

El cálculo del factorial de un número, es el método más recurrido para explicar la recursión. Supongamosque solamente sabemos la definición de factorial:

o El factorial de 0 (cero), es igual a 1 (caso base)
o El factorial de N, es igual a N multiplicado por el factorial de N-1 (llamada recursiva)Calculemos el factorial de 3

Factorial(3) = 3 x Factorial(3-1) // por definición
Factorial(3) = 3 x Factorial(2)

Pero ahora nos damos cuenta que desconocemos el factorial de 2, así que procedemosa calcularlo

Factorial(2) = 2 x Factorial(2-1) // por definición
Factorial(2) = 2 x Factorial(1)
Seguimos sin conocer el factorial de 3, de 2, y ahora de 1. Así que pasamos a calcular elfactorial de 1

Factorial(1) = 1 x Factorial(1-1) // por definición
Factorial(1) = 1 x Factorial(0)

Conocemos el factorial de 0 (cero) que es 1 (nuestro caso base), por lo que comenzamos a resolver e...