尾递归优化：Java中的尾递归实现

在以往解决需要递归求解的问题上一直使用传统递归，而不久前老师讲解了尾递归感觉需要记录一下(好记性不如烂笔头)

尾递归特点：在普通尾调用上，多出了2个特征。

1.在尾部调用的是函数自身(Self-called)

2.可通过优化，使得计算仅占常量栈空间(Stack Space)

举个例子：

斐波那契数列(Fibonacci sequence)，又称黄金分割数列、因数学家列昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3，n∈N*)在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。

下面代码仅求斐波那契数列的第n项为多少，而不求前n项和。

1 public classFibonacci {2

3 public static voidmain(String[] args) {4 int n = 50;5 long begin1 =System.currentTimeMillis();6 System.out.printf("%d\n", fibonacci(n));7 long end1 =System.currentTimeMillis();8 System.err.println("花费时间：" + (end1 - begin1) + "毫秒");9

10 long begin2 =System.currentTimeMillis();11 System.out.printf("%d\n", advanced(n, 0L, 1L));12 long end2 =System.currentTimeMillis();13 System.err.println("花费时间：" + (end2 - begin2) + "毫秒");14 }15

16 static long fibonacci(intn) {17 if (n < 0)18 return -1;19 if (n <= 1)20 returnn;21 return fibonacci(n - 1) + fibonacci(n - 2);22 }23

24 static long advanced(int n, long ret1, longret2) {25 if (n < 0)26 return -1;27 if (n == 0)28 returnret1;29 if (n == 1)30 returnret2;31 return advanced(n - 1, ret2, ret1 +ret2);32 }33

34 }

结果显示：

计算fibonacci数列第50项。

一些初学的想法：传统的递归相当于树状图计算，而尾递归相当于循环计算

譬如计算数字阶乘时：假设计算8！，传统递归理解为8*7*6*5*4*3*2*Factorial(1);递归函数中留有出口，直到递归到出口参数为1时才返回值。

尾递归相当于循环计算，我看做为循环递归。计算8！就循环8次。函数形如：

static long advanced(int n, intr) {if (n < 0) {return -1;

}else if (n == 0) {return 1 *r;

}else{return advanced(n - 1, r *n);

}

}

其中第一个参数为循环递归次数，第二个参数为每一步循环计算出的数，作为新的参数继续进行递归。(简单来说就是算出阶乘的每一步值作为新的参数)

函数返回自身函数，计算最终答案，进行下一函数计算时，不在依赖于上一函数，减少了栈空间的开辟。

ps：感觉类似于一串数的正反相乘过程。