我不是Lisp程序员，但我认为这会有所帮助。

基本上，这是一种编程风格，递归调用是最后一件事。

下面是一个使用尾部递归进行阶乘的常见Lisp示例。由于无堆栈的性质，人们可以进行疯狂的大型阶乘计算。。。

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

然后为了好玩，你可以尝试（格式化nil“~R”（！25））

尾部递归函数是一个递归函数，其中递归调用是函数中最后执行的事情。

常规递归函数，我们有堆栈，每次调用递归函数中的递归函数时，都会向调用堆栈添加另一层。在正常递归中空间：O（n）尾递归使空间复杂性从

O(N)=>O(1)

尾部调用优化意味着可以从另一个函数调用函数，而不增加调用堆栈。我们应该在递归解中编写尾部递归。但某些语言实际上不支持其引擎中的尾部递归，该引擎将语言向下编译。自从ecma6以来，规范中就有了尾部递归。但编译js的引擎都没有实现尾部递归。你无法在js中实现O（1），因为编译器本身不知道如何实现这种尾部递归。截至2020年1月1日，Safari是唯一支持尾部呼叫优化的浏览器。Haskell和Java具有尾部递归优化

正则递归阶乘

function Factorial(x) {
  //Base case x<=1
  if (x <= 1) {
    return 1;
  } else {
    // x is waiting for the return value of Factorial(x-1)
    // the last thing we do is NOT applying the recursive call
    // after recursive call we still have to multiply.
    return x * Factorial(x - 1);
  }
}

我们的调用堆栈中有4个调用。

Factorial(4); // waiting in the memory for Factorial(3)
4 * Factorial(3); //  waiting in the memory for Factorial(2)
4 * (3 * Factorial(2)); //  waiting in the memory for Factorial(1)
4 * (3 * (2 * Factorial(1)));
4 * (3 * (2 * 1));

我们正在进行4次Factorial（）调用，空间为O（n）这可能会导致堆栈溢出

尾部递归因子

function tailFactorial(x, totalSoFar = 1) {
  //Base Case: x===0. In recursion there must be base case. Otherwise they will never stop
  if (x === 0) {
    return totalSoFar;
  } else {
    // there is nothing waiting for tailFactorial to complete. we are returning another instance of tailFactorial()
    // we are not doing any additional computaion with what we get back from this recursive call
    return tailFactorial(x - 1, totalSoFar * x);
  }
}

在进行递归调用后，我们不需要记住任何内容

重要的一点是尾部递归本质上等同于循环。这不仅仅是一个编译器优化的问题，而是一个关于表现力的基本事实。这是双向的：你可以采取任何形式的循环

while(E) { S }; return Q

其中E和Q是表达式，S是语句序列，并将其转换为尾部递归函数

f() = if E then { S; return f() } else { return Q }

当然，必须定义E、S和Q来计算一些变量的有趣值。例如，循环函数

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

等效于尾部递归函数

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

（用参数较少的函数“包装”尾部递归函数是一种常见的函数习惯用法。）

术语文件对尾部递归的定义有这样的说法：

尾部递归/n/

如果您还没有厌倦它，请参阅尾部递归。

对我来说，理解尾调用递归的最好方法是递归的一种特殊情况，其中最后一个调用（或尾调用）是函数本身。

比较Python中提供的示例：

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^递归

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^尾部递归

正如您在常规递归版本中看到的，代码块中的最后一个调用是x+recsum（x-1）。所以在调用recsum方法之后，还有一个操作是x+。。。

然而，在尾部递归版本中，代码块中的最后一个调用（或尾部调用）是tailrecsum（x-1，running_total+x），这意味着最后一次调用是对方法本身进行的，之后不再进行操作。

这一点很重要，因为这里看到的尾部递归不会使内存增长，因为当底层VM看到一个函数在尾部位置（函数中要计算的最后一个表达式）调用自己时，它会消除当前堆栈帧，这就是所谓的尾部调用优化（TCO）。

EDIT

没有。请记住，上面的示例是用Python编写的，其运行时不支持TCO。这只是一个解释这一点的例子。在Scheme、Haskell等语言中支持TCO