With this code, I get stackoverflow (sorry for the pun):

 public double calculate(long n) { if (n <= 0) return 0; else return f.apply((double) n) + calculate(n); }

Is it possible to alter this recursion into tail recursion to avoid an error?

Whole class:

 public class MyFunction { private String title; private Function<Double, Double> f; public MyFunction(String title, Function<Double, Double> f) { this.title = title; this.f = f; } public String getTitle() { return title; } public Function<Double, Double> getFunction() { return f; } public double calculate(long n) { if (n <= 0) return 0; else return f.apply((double) n) + calculate(n); } }

Example of use:

 long N = (long) pow(10, 1000); MyFunction f1 = new MyFunction("test", x -> pow(x + 1, x + 0.1) / x); System.out.println(f1.calculate(N));
  • Where is the variable f , what is it generally needed for, and what really bothers you: a non-working code or tail recursion? - Regent
  • Completed the question - faoxis
  • Is java able to tail recursion? - Alexey Shimansky
  • @ Alexey Shimansky That's the question. Is it possible to do this, and if so, how. - faoxis
  • @faoxis looks like zRrr has already written what needs to be done - Alexey Shimansky

1 answer 1

You can convert your recursive algorithm to iterative, which will not cause a stack overflow. You can read in this answer . Recursion from your example in an iterative form:

 public double calculate(long n) { double sum = 0; if (n <= 0) return sum; while (n > 0) { sum += f.apply((double) n); n--; } return sum; }

UPD # 1

As for your question directly, in the comments you yourself gave the correct answer. The tail recursion will look like this:

 public double calculate(long n) { return calculate(n, 0); } public double calculate(long n, double sum) { return n <= 0 ? sum: calculate(n - 1, sum + f.apply((double) n)); }

I wrapped it in an overridden method so as not to change the code where the single-parameter method is used. Thus, when a program enters the else branch (of a ternary operator) again and again, we no longer need the actual stack — the program has everything it needs as arguments to the method in a recursive call.

UPD # 2

Indeed, as practice has shown, in Java 1.8 there is no tail recursion optimization (TRO). During the execution of the code, the stack is still expanded. I thought it might be possible to solve this issue using lambda functions, but failed and from now on we all plunge into the world of magic template functions =) Let's use the design jump pattern for jumping , which will convert stack-dependent recursion into the corresponding iterative algorithm. Since the cycles do not cause a stack descent, this can be considered as a form of chainless recursion. Here is the code to check:

 import java.lang.Math; import java.util.Optional; import java.util.function.Function; class Trampoline<T> { public T getValue() { throw new RuntimeException("Not implemented"); } public Optional<Trampoline<T>> nextTrampoline() { return Optional.empty(); } public final T compute() { Trampoline<T> trampoline = this; while (trampoline.nextTrampoline().isPresent()) { trampoline = trampoline.nextTrampoline().get(); } return trampoline.getValue(); } } final class StacklessRecursiveFunction { public static Trampoline<Double> createTrampoline(final double n, final double sum) { if (n <= 0) { return new Trampoline<Double>() { public Double getValue() { return sum; } }; } return new Trampoline<Double>() { public Optional<Trampoline<Double>> nextTrampoline() { return Optional.of(createTrampoline(n - 1, sum + Math.pow(n + 1, n + 0.1) / n)); } }; } } class MagicStacklessRecur{ public static void main(String[] args) { System.out.println(StacklessRecursiveFunction.createTrampoline(Math.pow(10,1000), 0).compute()); } }
  • In tail recursion, stackoverflow arises all the same. Does this mean that Java cannot avoid building stack extensions with it? - faoxis
  • one
    @faoxis a moment, I’ll do upd # 2 with checkout =) - Lex Hobbit
  • one
    @faoxis about it not so long ago there was an article on Habré . - Regent
  • @faoxis added upd # 2 - Lex Hobbit