Tail call optimization for fibonacci function in java

Question

I was studying about Tail call recursion and came across some documentation that mentioned. Sun Java doesn't implement tail call optimization. I wrote following code to calculate fibonacci number in 3 different ways: 1. Iterative 2. Head Recursive 3. Tail Recursive

public class Fibonacci {
    public static void main(String[] args) throws InterruptedException {
        int n = Integer.parseInt(args[0]);
        System.out.println("\n Value of n : " + n);
        System.out.println("\n Using Iteration : ");
        long l1 = System.nanoTime();
        fibonacciIterative(n);
        long l2 = System.nanoTime();
        System.out.println("iterative time = " + (l2 - l1));
        System.out.println(fibonacciIterative(n));

        System.out.println("\n Using Tail recursion : ");
        long l3 = System.nanoTime();
        fibonacciTail(n);
        long l4 = System.nanoTime();
        System.out.println("Tail recursive time = " + (l4 - l3));
        System.out.println(fibonacciTail(n));

        System.out.println("\n Using Recursion : ");
        long l5 = System.nanoTime();
        fibonacciRecursive(n);
        long l6 = System.nanoTime();
        System.out.println("Head recursive time = " + (l6 - l5));
    }

    private static long fibonacciRecursive(int num) {
        if (num == 0) {
            return 0L;
        }
        if (num == 1) {
            return 1L;
        }
        return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2);
    }

    private static long fibonacciIterative(int n) throws InterruptedException {
        long[] arr = new long[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            // Thread.sleep(1);
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    private static long fibonacciTail(int n) {
        if (n == 0)
            return 0;
        return fibHelper(n, 1, 0, 1);
    }

    private static long fibHelper(int n, int m, long fibM_minus_one, long fibM) {
        if (n == m)
            return fibM;
        return fibHelper(n, m + 1, fibM, fibM_minus_one + fibM);
    }
}

On running this program I drew some results:

Head Recursive method does not finish for n>50. Program looked like hanged. Any idea, why this could happen?
Tail recursive method took significantly less time as compared to Head recursion. Sometimes took even less time than Iterative method. Does it mean that java does some Tail call optimization internally? And if it does, why I did it give StackOverflowError at n > 5000?

System specs:

Intel core 5 processor,

Windows XP,

32 bit Java 1.6

Default stack size for JVM.

@CoolBeans If that is the case, sign me up for this professor — RichardTheKiwi, Mar 28 '11 at 00:08
At least one of IBM's JVM implementations performs tail call optimization if it's possible. http://stackoverflow.com/questions/105834/does-the-jvm-prevent-tail-call-optimizations and http://publib.boulder.ibm.com/infocenter/javasdk/v5r0/index.jsp?topic=/com.ibm.java.doc.diagnostics.50/html/jit_optimize.html — andersoj, Mar 28 '11 at 01:13
You should also observe that the `fibonacciRecursive` is _not_ head recursive, and you've coded it to have a different complexity than the other two. (No it didn't hang. It just takes twice as long to calculate 51 than 50, ergo, 1024 times as long to calculate 60 than 50.) — Mooing Duck, Oct 25 '11 at 19:13

score 12 · Answer 1 · answered Mar 28 '11 at 00:31

Does it mean that java does some Tail call optimization internally?

No, it does not. The HotSpot JIT compilers do not implement tail-call optimization.

The results you are observing are typical of the anomalies that you see in a Java benchmark that doesn't take account of JVM warmup. For instance, the "first few" times a method is called, it will be executed by the interpreter. Then the JIT compiler will compile the method ... and it will get faster.

To get meaningful results, put a loop around the whole lot and run it a number of times until the timings stabilize. Then discard the results from the early iterations.

... why I did it give StackOverflowError at n > 5000?

That's just evidence that there isn't any tail-call optimization happening.

score 3 · Answer 2 · answered Mar 28 '11 at 00:14

3

For the first question, what is 2^50 (or something close)? Each number N in a recursive Fib function calls it twice (prior 2). Each of those calls 2 prior iterations, etc.. so it's grows to 2^(N-k) of recursion (k is probably 2 or 3).

The 2nd question is because the 2nd one is a straight N recursion. Instead of going double headed (N-1),(N-2), it simply builds up from M=1, M=2... M=N. Each step of the way, the N-1 value is retained for adding. Since it is an O(N) operation, it is comparable to the iterative method, the only difference being how the JIT compiler optimizes it. The problem with recursion though is that it requires a huge memory footprint for each level that you stack onto the frame - you run out of memory or stack space at some limit. It should still generally be slower than the iterative method.

answered Mar 28 '11 at 00:14

RichardTheKiwi

105,798
26
196
262

Yea, I agree, the values are suspiciously close. – julx Mar 28 '11 at 00:17
So, it means, java didnt do any kind of optimization. The tail recursive method took O(n) which is same as iterative method. – TTP Mar 28 '11 at 00:27
Optimization in terms of stack usage. Some languages support Tail call optimizations which replace Tail recursive calls with jump instructions and save stack overflow errors. – TTP Mar 28 '11 at 00:44
@TTP - Stephen C has the answer – RichardTheKiwi Mar 28 '11 at 02:01

score 2 · Answer 3 · answered Mar 28 '11 at 00:15

2

Regarding point 1: Computing Fibonacci numbers recursively without memoization leads to a run time that is exponential in n. This goes for any programming language that does not automatically memoize function results (such as most mainstream non-functional languages, e.g. Java, C#, C++, ...). The reason is that the same functions will get called over and over again - e.g. f(8) will call f(7) and f(6); f(7) will call f(6) and f(5), so that f(6) gets called twice. This effect propagates and causes an exponential growth in the number of function calls. Here's a visualization of which functions get called:

f(8)
 f(7)
  f(6)
   f(5)
    f(4)
     ...
    f(3)
     ...
   f(4)
    ...
  f(5)
   f(4)
    ...
   f(3)
    ...
 f(6)
  f(5)
   ...
  f(4)
   ...

answered Mar 28 '11 at 00:15

Aasmund Eldhuset

37,289
4
68
81

Thanks Aasmund. You are correct. So recursive method has running time of O(c^n) which increases exponentially as n increases. – TTP Mar 28 '11 at 00:33
1

@TTP: Yes. However, this effect isn't really due to the head recursion, but to the fact that the recursive method calls itself _twice_, and that it ends up getting called many times for the same argument value, and that it "forgets" which values it has already calculated. If you use [memoization](http://en.wikipedia.org/wiki/Memoization), you get linear runtime. – Aasmund Eldhuset Mar 28 '11 at 00:38

score 2 · Answer 4 · answered Dec 04 '11 at 00:47

You can use Memoization to avoid head recursion.

I have tested the following code , when N <=40 , that approach is bad because Map has trade-off.

private static final Map<Integer,Long> map = new HashMap<Integer,Long>();

private static long fibonacciRecursiveMemoization(int num) {
    if (num == 0) {
        return 0L;
    }
    if (num == 1) {
        return 1L;
    }

    int num1 = num - 1;
    int num2 = num - 2;

    long numResult1 = 0;
    long numResult2 = 0;

    if(map.containsKey(num1)){
        numResult1 = map.get(num1);
    }else{
        numResult1 = fibonacciRecursiveMemoization(num1);
        map.put(num1, numResult1);
    }

    if(map.containsKey(num2)){
        numResult2 = map.get(num2);
    }else{
        numResult2 = fibonacciRecursiveMemoization(num2);
        map.put(num2, numResult2);
    }

    return numResult1 + numResult2;
}

when the value of n : 44

Using Iteration : iterative time = 6984

Using Tail recursion : Tail recursive time = 8940

Using Memoization Recursion : Memoization recursive time = 1799949

Using Recursion : Head recursive time = 12697568825

Tail call optimization for fibonacci function in java

4 Answers4