许多人已经在这里解释了递归。我想引用Riccardo Terrell的《.NET中的并发性，并发和并行编程的现代模式》一书中关于递归的一些优点的一些想法：

“函数递归是FP中迭代的自然方式，因为它避免状态突变。在每次迭代期间，都会传递一个新值而不是被更新（变异）。在里面此外，可以编写递归函数，使您的程序更加模块化，并引入了开发机会并行化。"

以下是同一本书中关于尾部递归的一些有趣注释：

尾部调用递归是一种转换规则递归的技术函数转换为可处理大型输入的优化版本没有任何风险和副作用。注：尾部调用作为优化的主要原因是提高数据位置、内存使用率和缓存使用率。通过做尾巴调用时，被调用者使用与调用者相同的堆栈空间。这减少了记忆压力。它略微改善了缓存，因为存储器被后续调用方重用，并且可以留在缓存中，而不是驱逐旧的缓存线，为新的缓存腾出空间线

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

比较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

这意味着不需要将指令指针推到堆栈上，只需跳到递归函数的顶部并继续执行即可。这允许函数无限递归而不会溢出堆栈。

我写了一篇关于这个主题的博客文章，里面有堆栈框架的图形示例。

这本摘自《Lua编程》一书的摘录展示了如何进行正确的尾部递归（在Lua中，但也应适用于Lisp）以及为什么它更好。

尾部调用[尾部递归]是一种goto-dressed作为呼叫。当函数调用另一个作为其最后一个行动，所以它没有其他事情可做。例如在以下代码中，对g的调用是尾调用：函数f（x）返回g（x）终止在f调用g之后，它没有其他内容在这种情况下，程序不需要返回调用函数时调用的函数末端。因此在尾呼之后，程序不需要保留任何有关调用函数的信息在堆栈中。。。因为正确的尾呼使用no堆栈空间一个程序可以生成。例如，我们可以使用任意数字作为自变量；它永远不会溢出堆栈：函数foo（n）如果n>0，则返回foo（n-1）end终止…正如我前面所说的，尾呼是有点后顾之忧。因此，一个非常有用的正确的尾部调用在Lua用于编程状态机。此类应用程序可以代表功能状态；更改状态是去（或打电话）一个特定的作用例如，让我们考虑一个简单的迷宫游戏。迷宫有几个房间，每个房间最多四个门：北、南、东和西在每个步骤中，用户输入移动方向。如果有门在该方向上，用户将相应的房间；否则程序打印警告。目标是从最初的房间到最后的房间房间该游戏是典型的状态机，其中当前房间是状态。我们可以用一个每个房间的功能。我们用尾巴从一个房间移动到另一个有四个房间的小迷宫可能看起来像这样：功能室1（）本地移动=io.read（）如果移动==“南”，则返回房间3（）elseif move==“east”然后返回room2（）否则打印（“无效移动”）返回房间1（）--呆在同一个房间终止终止功能室2（）本地移动=io.read（）如果move==“south”，则返回room4（）elseif move==“west”然后返回房间1（）否则打印（“无效移动”）返回室2（）终止终止功能室3（）本地移动=io.read（）如果move==“north”，则返回room1（）elseif move==“east”然后返回room4（）否则打印（“无效移动”）返回室3（）终止终止功能室4（）打印（“恭喜！”）终止

因此，当您进行如下递归调用时：

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

这不是尾部递归的，因为在进行递归调用之后，您仍然需要在该函数中做一些事情（添加1）。如果输入的数字很高，可能会导致堆栈溢出。

递归意味着函数调用自身。例如：

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

尾部递归是指结束函数的递归：

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

看，非终结函数（Scheme术语中的过程）做的最后一件事就是调用自己。另一个（更有用的）例子是：

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

在helper过程中，如果左边不是nil，最后一件事就是调用自己（AFTER cons something和cdr something）。这基本上就是如何映射列表的。

尾部递归有一个很大的优点，即解释器（或编译器，取决于语言和供应商）可以对其进行优化，并将其转换为相当于while循环的东西。事实上，在Scheme传统中，大多数“for”和“while”循环都是以尾部递归的方式完成的（据我所知，没有for和while）。

这里是前面提到的tailrecsum函数的Perl 5版本。

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}