递归： 就是函数调用自己。 func() { foo(); func(); bar(); }
尾调用：就是在函数的最后，调用函数（包括自己）。 foo(){ return bar(); }
尾递归：就是在函数的最后，调用自身。 func() { foo(); return func(); }
尾递归是递归的优化，优化的目的是栈深度=1，永不*。所有的递归都能转成尾递归。简单的场景，比如计算阶乘N!和Fibonacci数列，可以用parameter代替临时变量，实现尾递归。复杂的场景，比如对二叉树进行先序遍历(pre-order traversal, 深度优先遍历)，就需要使用Continuation Passing Style(CPS)才能实现尾递归。
简单的场景比较好理解，定义里有多少个递归的临时变量，就用多少个参数即可。比如：
//阶乘：N! = (N-1)! * N
static int Factorial_TailRecursion(int target, int total = 1) {
if (target <= 1) {
return total;
} else {
return Factorial_TailRecursion(target - 1, total * target);
}
}
//Fibonacci数列：f(n) = f(n-1) + f(n-2)
static int Fibonacci_TailRecursion(int target, int n1 = 0, int n2 = 1) {
if (target <= 0) {
return n1;
} else {
return Fibonacci_TailRecursion(target - 1, n2, n1 + n2);
}
}
至于CPS的写法，比如func(int i, Func<int, int> continuation)，要这么看：用func处理i返回的结果，还需要继续用continuation处理，这就是继续(Continuation)的含义。仍然以这个例子为例：
static int Factorial_Continuation(int target, Func<int, int> func) {
if (target <= 1) {
return func(1);
} else {
//以5为例，计算Fac(4)的值，后续*5再传入func
return Factorial_Continuation(target - 1, n => func(n * target));
}
}
static int Fibonacci_Continuation(int target, Func<int, int> func) {
if (target < 2) {
return func(target);
} else {
//以5为例，计算Fib(4)的值、后续计算Fib(3)的值、两值相+再传入func
return Fibonacci_Continuation(target - 1,
r1 => Fibonacci_Continuation(target - 2,
r2 => func(r1 + r2)));
}
}