5

Tengo el siguiente problema de overflow al ejecutarlo con numeros algo grandes y eso que puse long en lugar de int, ¿como puedo solucionarlo?

public static long NI(long n){
    if (n==1)
        return 1;
    else
        return NI(n-1)+(2*n-1);
}

public static void main(String[] args) {
    Scanner sc = new Scanner (System.in);
    long num = sc.nextLong();

    System.out.println(NI(num));
    sc.close();
}

el error es el siguiente

Exception in thread "main" java.lang.StackOverflowError
    at NumImpares.NI(NumImpares.java:6)
    at NumImpares.NI(NumImpares.java:9)
    at NumImpares.NI(NumImpares.java:9)

la linea 6 es el if y la linea 9 el return recursivo.

2
  • Puedes mostrar el stack del error?
    – solamente
    Commented el 14 mar. 2019 a las 20:29
  • Una pregunta, ¿la formula que expones es correcta? Me refiero a que no es lo mismo (2 * (n - 1)) y ((2 * n) - 1). Tal como la planteas y de acuerdo al orden de precedencia, tu fórmula equivale a la la segunda opción. ¿Puedes aclarar eso? Saludos. Commented el 15 mar. 2019 a las 7:48

1 respuesta 1

2

Explicar en pocas palabras el problema que afrontas y la solución al mismo no es tarea fácil.


TCO (Optimización de cola)

Primero voy a mencionar algo llamado TCO (Tail Call Optimization) o traducido al español: optimización de llamada de cola.

La mayoría de lenguajes funcionales como Erlang utilizan o implementan una optimización TCO.

Java por su parte no lo hace. Debido más que nada a un tema de seguridad en la ejecución de ciertos métodos (normalmente la optimización de cola implementa una instrucción de salto (jump) que le permite a la subrutina llamada en la cola de la recursión devolver inmediatamente el control a la rutina desde la cual fue llamada).

Para una mejor explicación de la TCO puedes leer el siguiente post: On Tail Call Optimisation, está en inglés pero vale la pena leerlo. (Me da la idea de escribir uno en español)


TAIL RECURSION (Recursión de cola)

Ahora, volviendo a tu problema, existen algunas formas de resolverlo.

En tu rutina tienes lo siguiente:

return NI(n-1)+(2*n-1);

Es efectivamente una llamada recursiva a la función NI, sin embargo, luego de la llamada, realizas una suma, por lo tanto la llamada recursiva no está en la cola. Así, tu proceso recursivo no es el conocido como recursividad de cola.

Como mencioné anteriormente, tienes algunas formas de resolver el problema, aquí algunas:

  • Usas el método recursivo para una cantidad relativamente pequeña de llamadas. Esto implica que (dependiendo del sistema) puedes usar el método para valores en un rango que se considere seguro. Lamentablemente, debido a que el stack es variable en cada sistema, no puedo decirte cuál es el número seguro de llamadas. Tal vez para unas pocas miles no tengas problemas, pero ya en decenas de miles la cosa cambia.
  • Usas la recursividad para casos en los que sabes que no se produzcan desbordamientos de pila. Nuevamente esto va a depender del resultado que esperes obtener.
  • Incrementas el valor o tamaño del stack. Tal vez esto sea tentador, pero no es nada óptimo.
  • Usas un lenguaje que implemente TCO. Esta solución es algo abrupta. Pero todo sea por obtener un resultado favorable.
  • Escribes tu propia pseudo optimización. Esta solución requiere algo de conocimientos un poco avanzados. Pero te garantizo que es una buena solución.
  • Alguna otra que se me escape, y que tal vez alguien con mayor experiencia que yo pueda añadir como respuesta.

SOLUCIÓN

Para poder implementar una solución al problema haremos 2 cosas:

  1. Replantear tu función para poder aplicar una recursividad de cola.
  2. Escribir una implementación básica de TCO para usar con JAVA.

Tu programa calcula el cuadrado de un número (cosa muy trivial usando el operador ^), lo hace mediante la serie matemática: n^2 = (2*n - 1) + (2*(n-1) - 1) + ... + 1. Para valores de n > 1.

Usando esta información vamos a escribir una función de tal manera que podamos llamarla en la cola de nuestra subrutina.

Normalmente, las funciones de este tipo suelen usar un parámetro llamado acumulador, que permitirá acumular el valor que deseamos devolver al final del proceso recursivo.

Yo, particularmente opto por definir una función helper que será la encargada de usar el parámetro acumulador.

Nuestra función helper tendrá 2 parámetros. El primer parámetro será el valor de n, y el segundo parámetro será el valor 1. El valor del segundo parámetro inicialmente será lo que se conoce como valor acumulado para el caso base. En nuestra función, el caso base será n <= 1.

Lo que haremos es incluir la suma (que tu realizas externamente a tu función) dentro de la misma función como un parámetro.

Nuestra función helper quedará de la siguiente manera:

private static long helper(long n, long acc) {
    return n < 2
    ? acc
    : helper(n - 1, acc + 2*n - 1);
}

Nota: Puedes observar que uso la versión simplificada del if ... else, usando el operador ternario ? :

Ahora, vamos a escribir una función llamada cuadrado que, como su nombre indica, devolverá el cuadrado de un numero. Esta función simplemente es una lanzadera para llamar a nuestra función helper.

public static long cuadrado(long n) {
    return helper(n, 1);
}

Tan sencillo como eso. Ya hemos escrito nuestra función con llamada de cola.

Si JVM implementara una TCO, entonces no deberíamos preocuparnos por el desbordamiento de la pila.

Pero, como señalé anteriormente este no es el caso.

Una implementación completa del programa podría quedar de la siguiente manera:

import java.util.Scanner;

public class cuadradoRecursivo {
    public static long cuadrado(long n) {
        return helper(n, 1);
    }
    private static long helper(long n, long acc) {
        return n < 2
        ? acc
        : helper(n - 1, acc + n*2 - 1);
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.println("Introduzca un entero positivo:");
        long num = sc.nextLong();
        long resultado = cuadrado(num);
        System.out.println("El cuadrado de " + num + " es " + resultado);
    }
}

En mi sistema, cuando ejecuto el programa se produce un desbordamiento de pila (Stack Overflow) para valores de n cercanos a 12000. Tomando en cuenta que el valor máximo para el tipo long es 9.223.372.036.854.775.807 (usando . como separador de miles), y dado que el cuadrado de 12000 es 144.000.000, vemos que el problema del desbordamiento de pila no es por la magnitud del resultado, que en todo caso nos daría otro tipo de error, sino que el problema es debido a la falta de optimización del proceso recursivo de cola (TCO).

Entonces vamos a escribir nuestra propia optimización de TCO.

Para esto vamos a escribir una clase que simulará los procesos computacionales de una TCO.

No puedo darme el crédito por escribir dicha clase, aunque entiendo el proceso que involucra. Esta solución al problema de la TCO en Java la conseguí en Functional Programming in Java

¿Cómo funciona? Explicarlo no es tan sencillo, la idea es crear una clase que sea determinística, es decir, que pueda determinar el estado en el que se encuentra nuestra llamada recursiva. Usaremos una clase a la que llamaremos Suspend y otra que llamaremos Return. La clase Suspend representará el paso intermedio en la recursión, cuando el proceso está "suspendido" esperando a que se realice la siguiente llamada recursiva. La clase Result representa el paso final, cuando se devuelve el valor de la última llamada recursiva.

De esta forma podremos realizar llamadas recursivas que no desbordarán la pila, ya que estaremos eliminando de la pila los elementos innecesarios.

Una implementación de dicha clase puede ser la siguiente:

import java.util.function.Supplier;

public abstract class TailCall<T> {
  public abstract TailCall<T> resume();
  public abstract T eval();
  public abstract boolean isSuspended();
  private TailCall() {};

  public static class Return<T> extends TailCall<T> {
    private final T t;
    private Return(T t) {
      this.t = t;
    }
    @Override
    public T eval() {
      return t;
    }
    @Override
    public boolean isSuspended() {
      return false;
    }
    @Override
    public TailCall<T> resume() {
      throw new IllegalStateException("Return has no resume");
    }
  }
  public static class Suspend<T> extends TailCall<T> {
    private final Supplier<TailCall<T>> resume;
    private Suspend(Supplier<TailCall<T>> resume) {
      this.resume = resume;
    }
    @Override
    public T eval() {
      TailCall<T> tailRecursion = this;
      while(tailRecursion.isSuspended()) {
        tailRecursion = tailRecursion.resume();
      }
      return tailRecursion.eval();
    }
    @Override
    public boolean isSuspended() {
      return true;
    }
    @Override
    public TailCall<T> resume() {
      return resume.get();
    }
  }
  public static <T> Return<T> ret(T t) {
    return new Return<>(t);
  }
  public static <T> Suspend<T> sus(Supplier<TailCall<T>> s) {
    return new Suspend<>(s);
  }
}

Como puedes apreciar, no es nada trivial.

Por último, una implementación del programa podría quedar de la siguiente manera:

import java.util.Scanner;

public class cuadradoRecursivo {
  public static long cuadrado(long n) {
    return helper(n, 1).eval();
  }
  private static TailCall<Long> helper(long n, long acc) {
    return n < 2
    ? TailCall.ret(acc)
    : TailCall.sus(() -> helper(n - 1, acc + n*2 - 1));
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Introduzca un numero entero positivo:");
    long num = sc.nextLong();
    long resultado = cuadrado(num);
    System.out.println("El cuadrado de " + num + " es: " + resultado);
  }
}

Como puedes ver, no solo estoy usando la clase que me permite optimizar la recursividad, sino que además estoy usando una expresión lambda (función anónima), que es lo que normalmente se emplea en lenguajes funcionales.

Nota: Recuerda que debes tener el archivo TailCall.java en el mismo directorio que se encuentra tu archivo cuadradoRecursivo.java

Con esta implementación puedes ejecutar tranquilamente tantas llamadas recursivas como desees. Aunque recuerda que tienes un límite en el valor máximo que puedes representar usando un tipo long en Java.

No se si esta solución es satisfactoria a las pruebas que dices debe superar el programa. Tal vez exista otra forma de realizar la tarea que se ajuste a las pruebas que requiere tu programa, y esto es un cañón para matar un mosquito. Pero en recursividad es poco lo que puedes hacer sin no dispones de una TCO.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.