métodos recursivos

Se dice que un método es recursivo cuando se llama a sí mismo

public int factorial(int n) {     if (n < 1)         return 1;     else         return n * factorial(n-1); }
factorial( 5 ) = 5 * factorial( 4 )                = 5 * ( 4 * factorial( 3 ) )                = 5 * ( 4 * (3 * factorial( 2 ) ) )                = 5 * ( 4 * (3 * (2 * factorial( 1 ) ) ) )                = 5 * ( 4 * (3 * (2 * ( 1 * factorial( 0 ) ) ) ) )                = 5 * ( 4 * (3 * (2 * ( 1 * 1 ) ) ) )                = 5 * 4 * 3 * 2 * 1 * 1                = 120

 

Este tipo de programas funciona porque cada método tiene sus propias variables locales (argumentos). En cada llamada se crea una variable propia y diferente de otras.

Los métodos recursivos se prestan a errores de programación si el creador no se asegura de que en ejecución el número de llamadas termina alguna vez. El código anterior podría estar mal en pequeños detalles que darían lugar a una recursión sin fin:

 

public int factorial(int n) {     if (n < 1)         return 1;     else         // modificamos la copia local, pasando el mismo n         return n * factorial(n--); }
public int factorial(int n) {     if (n == 0)                       // falla si llamamos con n < 0         return 1;     else         return n * factorial(n-1);    }

 

Si erramos en la condición de parada y el método se llama recursivamente sin fin, agotaremos la memoria disponible para ejecución y java lanzará una excepción StackOverflowError.

Es prácticamente obligatorio que los métodos recursivos incluyan código condicional. De hecho, en su diseño hay que tener en cuanta dos criterios:

1.       en cada llamada recursiva debemos acercarnos a la solución: convergencia

2.       debe haber un caso “cero”: terminación

Los métodos recursivos reflejan en programación la técnica de demostración por inducción de las matemáticas.

Los programas recursivos tienen cierta fama, no siempre merecida, de lentos. Aunque conviene medir tiempos antes de opinar, es cierto que en ocasiones la solución recursiva es muy elegante pero discutiblemente eficiente.

Existe una forma de plantear métodos recursivos que frecuentemente ayuda a mejorar el tiempo de ejecución. Se conoce como “tail recursion” y consiste en evitar que un método tenga que hacer algo tras conocer el resultado de la llamada recursiva; es decir, que lo último que haga un método sea llamarse recursivamente. El método anterior usando esta técnica quedaría así

 

public int factorial(int n) {     return factorial2(n, 1); }   private int factorial2(int n, int resultado) {     if (n < 1)         return resultado;     else         return factorial2(n-1, resultado*n); }

 

No obstante, si es necesario evitar la recursión, siempre puede pasarse a una estructura de bucles que refleje el mismo razonamiento recursivo:

 

public int factorial(int n) {     int resultado = 1;     while (n >= 1) {         resultado*= n;         n-= 1;     }     return resultado; }

 

Temas relacionados

115. Método [method] (concepto)

---