尽管您经常看到以下示例作为将阶乘转换为尾部调用的示例：

int factorial(int n, int acc=1) {
  if (n <= 1) return acc;
  else        return factorial(n-1, n*acc);
}

这不是很正确，因为它要求乘法同时具有关联性和可交换性。（乘法 是
关联的和可交换的，但是上面的方法不能作为不满足这些约束的其他操作的模型。）更好的解决方案可能是：

int factorial(int n, int k=1, int acc=1) {
  if (n == 0) return acc;
  else        return factorial(n-1, k+1, acc*k);
}

这也可以作为斐波那契变换的模型：

int fibonacci(int n, int a=1, int b=0) {
  if (n == 0) return a;
  else        return fibonacci(n-1, a+b, a);
}

请注意，它们从头开始计算序列，而不是在调用堆栈中排队未决的继续。因此，它们在结构上更像是迭代解决方案，而不是递归解决方案。但是，与迭代程序不同，它们从不修改任何变量。所有绑定都是恒定的。这是一个有趣且有用的属性。在这些简单的情况下，它并没有太大的区别，但是编写代码时无需重新分配就可以使一些编译器优化更加容易。

无论如何，最后一个确实为您的递归函数提供了一个模型。像斐波那契数列一样，我们需要保留相关的过去值，但是我们需要三个而不是两个：

int mouse(int n, int a=1, int b=1, int c=1) {
  if (n <=2 ) return a;
  else        return mouse(n-1, a*c+1, a, b);
}

附加物

在评论中，提出了两个问题。我将在这里回答他们（还有一个）。

首先，应该清楚（考虑到没有函数调用概念的基础机器体系结构），任何函数调用都可以改写为goto（可能是无边界的中间存储）。此外，任何goto都可以表示为尾叫。因此有可能（但不一定很漂亮）将任何递归重写为尾递归。

通常的机制是“连续传递样式”，这是一种奇特的说法，即每次您要调用函数时，您都将当前函数的其余部分打包为新函数（“连续”），然后传递该函数。到被调用函数的延续。由于每个函数随后都将连续性作为参数接收，因此它必须通过调用接收到的连续性来完成其创建的任何连续性。

那可能足以使您的头旋转，所以我换一种说法：将参数和延续位置推入堆栈，而不是将参数和返回位置推入堆栈并调用一个函数（稍后将返回），并转到一个函数，该函数随后将转到继续位置。简而言之，只需将堆栈作为显式参数，然后就无需返回。这种编程风格在事件驱动的代码中很常见（请参阅Python
Twisted），并且编写（和阅读）确实很痛苦。因此，我强烈建议让编译器为您执行此转换，如果您可以找到可以做到的转换。

@xxmouse 建议我从帽子中取出递归方程，并询问它是如何得出的。它只是原始的递归，但重新定义为单个元组的转换：

fn = fn-1*fn-3 + 1 => Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>

我不知道这是否更清楚，但这是我能做的最好的。看一下斐波那契示例，情况稍微简单一些。

@j_random_hacker
询问此转换的限制是什么。它适用于递归序列，其中每个元素可以由先前k元素的某些公式表示，其中k是一个常数。还有其他方法可以产生尾调用递归。例如：

// For didactic purposes only
bool is_odd(int n) { return n%2 == 1; }

int power(int x, int n, int acc=1) {
  if (n == 0)         return acc;
  else if (is_odd(n)) return power(x, n-1, acc*x);
  else                return power(x*x, n/2, acc);
}

上面的是 不 一样的通常的非尾调用递归，它不乘法的不同（但等效的和等长的）序列。

int squared(n) { return n * n; }

int power(int x, int n) {
  if (n == 0)         return 1;
  else if (is_odd(n)) return x * power(x, n-1));
  else                return squared(power(x, n/2));
}

感谢Alexey Frunze进行以下测试：输出（ideone）：

mouse(0) = 1
mouse(1) = 1
mouse(2) = 1
mouse(3) = 2
mouse(4) = 3
mouse(5) = 4
mouse(6) = 9
mouse(7) = 28
mouse(8) = 113
mouse(9) = 1018