递归与尾递归_java 将递归换乘尾递归

尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，深层函数所面对的不是越来越简单的问题，而是越来越复杂的问题——因为参数里带有前面若干步的运算路径。对于阶乘而言，越深并不意味着越复杂。

从时间和空间效率上看，尾递归和传统递归差不多。递归运算效率低主要是分支巨大，像阶乘这类单分支的递归，效率并不低。递归运算的深度和运算总量大致成指数关系，return多次并不会造成显著的性能损失。

一言以蔽之，传统递归越深，距离目标越近；尾递归越深，距离起点越远。

尾递归适用于运算对当前递归路径有依赖的问题，传统递归适用于运算对更深层递归有依赖的问题。

fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

fibTail :: Int-> Integer -> Integer -> Integer
fibTail 0 a b = 0
fibTail 1 a b = a
fibTail n a b = fibTail (n-1) (a+b) a

{-
fn f1 f0 = fn-1 (f0+f1) f1 = fn-1 f2 f1 = fn-2 (f1+f2) f2 = fn-2 f3 f2 =
fn-3 (f2+f2) f2 = fn-3 f3 f2 = ... = f1 fn fn-1
注意看， 第二个参数， 其实第二个参数就在做fib序列的运算。
尾递归一定是从初始值算起的，其实本质就是一个循环。
因为尾递归要求递归函数的返回值不再作为任何运算输入，所以堆栈可以不保留。
所以尾递归就是通过参数传递运算结果，而运算结果一定是从初始值开始运算的。
fib n 1 0 = fib (n - 1) 1 1
fib n-1 1 1 = fib(n-2) 2 1
fib n-2 2 1 = fib(n-3) 3 2
fib n-3 3 2 = fib(n-4) 5 3
-}

再如：
factor :: Integer -> Integer
factor 0 = 1
factor n = n * factor (n-1)

factorTail 0 v = v
factorTail n v = factorTail (n-1) (n * v)

所以， 尾递归对调用时的初识参数设置是有要求的， 故最好在封装一下:
myfactorTail n = factorTail n 1
myfib n = fibTail n 1 0