什么是尾递归？

下面是一个快速对比两个函数的代码片段。第一个函数使用传统递归来找到给定数字的阶乘。第二个函数使用尾递归。

非常简单易懂。

判断一个递归函数是否是尾递归，一种简单的方法是看它在基本情况下是否返回具体值，也就是说，不会返回1、true或任何类似的东西，而很可能返回某个方法参数的变体。

另一种方法是观察递归调用是否不涉及加法、算术运算、修改等，也就是说，它只是一个纯粹的递归调用。

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

递归函数是一种调用自身的函数。

它允许程序员使用最少量的代码编写高效的程序。

缺点是如果没有正确编写，它们可能会导致无限循环和其他意外结果。

我将解释简单递归函数和尾递归函数。

为了编写一个简单的递归函数：

1. 第一点要考虑的是何时决定退出循环，这就是 if 循环
2. 第二个问题是如果我们是自己的函数，则要执行什么过程

从给定的示例中：

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

从上面的例子可以看出

if(n <=1)
     return 1;

决定何时退出循环的因素。

else 
     return n * fact(n-1);

实际处理需要完成什么任务

让我逐一分解任务以便易于理解。

如果我运行fact(4)，让我们看看内部会发生什么

1. 将n替换为4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If语句执行失败就进入else循环，因此它返回4 * fact(3)

2. 在堆栈内存中，我们有4 * fact(3)

   将n替换为3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If循环失败，则进入else循环

所以它返回3 * fact(2)

请记住我们调用了```4 * fact(3)``

fact(3)的输出 = 3 * fact(2)

到目前为止，堆栈中有4 * fact(3) = 4 * 3 * fact(2)

3. 在堆栈内存中，我们有4 * 3 * fact(2)

   将n=2代入

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If循环失败，则进入else循环

所以返回2 * fact(1)

记得我们调用了4 * 3 * fact(2)

fact(2)的输出为2 * fact(1)

到目前为止，堆栈中有4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. 在栈内存中，我们有4 * 3 * 2 * fact(1)

   将 n=1 替换

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If循环为true

所以它返回1

请记住我们调用了4 * 3 * 2 * fact(1)

fact(1) = 1的输出

到目前为止，堆栈中有4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

最终，fact(4) = 4 * 3 * 2 * 1 = 24的结果是

尾递归将是

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

1. 将n替换为4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If语句失败，因此进入else语句，然后返回fact(3, 4)

2. 在堆栈内存中，我们有fact(3, 4)

   替换n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If 循环失败，则进入 else 循环

因此返回 fact(2, 12)

2. 在堆栈内存中，我们有 fact(2, 12)

   将 n 替换为 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If 循环为真，则返回 running_total

当 running_total = 24 时，输出结果如下

最终，fact(4,1) = 24

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

与标准递归实现相比，这种方法形成鲜明对比：

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

我不是Lisp程序员，但我认为这个链接可以帮助你。

基本上，它是一种编程风格，其中递归调用是你做的最后一件事。

尾递归函数是一种递归函数，其中在返回之前最后执行的操作是进行递归函数调用。也就是说，递归函数调用的返回值会被立即返回。例如，你的代码应该像这样：

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

实现尾调用优化或尾调用消除的编译器和解释器可以优化递归代码，以防止堆栈溢出。如果您的编译器或解释器不实现尾调用优化（例如CPython解释器），则以这种方式编写代码没有额外的好处。

例如，这是Python中标准的递归阶乘函数：

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

这是一个尾递归版本的阶乘函数：

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

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

然后，为了好玩，您可以尝试(format nil "~R" (! 25))

尾递归是指递归函数在函数结尾处（“尾部”）调用自身，且在递归调用返回后不做任何计算。许多编译器会将递归调用优化为尾递归或迭代调用。

考虑计算一个数的阶乘问题。

一种直接的方法是：

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

factTail(4)的递归树如下：

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

同样，在这里，最大递归深度是O(n)，但是没有任何调用会向堆栈添加额外的变量。因此编译器可以省略堆栈。

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

我写了一篇长篇文章，标题为"理解尾递归-Visual Studio C++-汇编视图"