关于递归还需要了解的是尾递归调用,尾递归调用是可以被进行优化的。
尾调用指的是一个方法或者函数的调用在另一个方法或者函数的最后一条指令中进行。下面定义了一个foo()函数作为例子:
int foo(int a) {
a = a + 1;
return func(a);
}
尾调用,不只是尾递归,函数调用本身都可以被优化掉,变得跟goto操作一样。这就意味着,在函数调用前先把栈给设置好,调用完成后再恢复栈的这个操作(分别是prolog和epilog)可以被优化掉。
public class RecursiveTest {
/**
* 递归实现
*
* @param n
* @return
*/
public static double recursive(long n) {
if (n == 1) {
return Math.log(1);
} else {
return Math.log(n) + recursive(n - 1);
}
}
/**
* 非递归实现
*
* @param n
* @return
*/
public static double directly(long n) {
double result = 0;
for (int i = 1; i <= n; i++) {
result += Math.log(i);
}
return result;
}
public static void main(String[] args) {
int i = 5000000;
long test = System.nanoTime();
long start1 = System.nanoTime();
double r1 = recursive(i);
long end1 = System.nanoTime();
long start2 = System.nanoTime();
double r2 = directly(i);
long end2 = System.nanoTime();