递归： 就是函数调用自己。 func() { foo(); func(); bar(); }

尾调用：就是在函数的最后，调用函数（包括自己）。 foo(){ return bar(); }

尾递归：就是在函数的最后，调用自身。 func() { foo(); return func(); }

尾递归是递归的优化，优化的目的是栈深度=1，永不StackOverflow。所有的递归都能转成尾递归。简单的场景，比如计算阶乘N!和Fibonacci数列，可以用parameter代替临时变量，实现尾递归。复杂的场景，比如对二叉树进行先序遍历(pre-order traversal, 深度优先遍历)，就需要使用Continuation Passing Style(CPS)才能实现尾递归。

简单的场景比较好理解，定义里有多少个递归的临时变量，就用多少个参数即可。比如：

//阶乘：N! = (N-1)! * Nstatic 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
    
      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
     
       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)));    }}
     
    

参考