Я изучал рекурсию Tail call и наткнулся на некоторые упомянутые документы. Sun Java не реализует оптимизацию хвостовых вызовов. Я написал следующий код для вычисления числа фибоначчи тремя разными способами: 1. Итеративный 2. Рекурсивная головка 3. Рекурсивный хвост
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);
}
}
При запуске этой программы я получил некоторые результаты:
- Головной рекурсивный метод не заканчивается для n > 50. Программа выглядела как повешенная. Любая идея, почему это может произойти?
- Рекурсивный метод хвоста занимал значительно меньше времени по сравнению с рекурсией головы. Иногда требуется меньшее время, чем Iterative method. Означает ли это, что java делает внутреннюю оптимизацию Tail? И если это так, то почему я это сделал, это дает StackOverflowError при n > 5000?
Системные спецификации:
Процессор Intel Core 5,
Windows XP,
32-разрядная версия Java 1.6
Размер стека по умолчанию для JVM.
