【尾递归实现，对递归的优化】求1+2!+3!+...+N!的和 （C++代码）

解题思路:了解尾递归：

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

为了理解尾递归是如何工作的，让我们再次以递归的形式计算阶乘。首先，这可以很容易让我们理解为什么之前所定义的递归不是尾递归。回忆之前对计算n!的定义：在每个活跃期计算n倍的(n－1)!的值，让n=n－1并持续这个过程直到n=1为止。这种定义不是尾递归的，因为每个活跃期的返回值都依赖于用n乘以下一个活跃期的返回值，因此每次调用产生的栈帧将不得不保存在栈上直到下一个子调用的返回值确定。现在让我们考虑以尾递归的形式来定义计算n!的过 [1]  程。

这种定义还需要接受第二个参数a，除此之外并没有太大区别。a（初始化为1）维护递归层次的深度。这就让我们避免了每次还需要将返回值再乘以n。然而，在每次递归调用中，令a=na并且n=n－1。继续递归调用，直到n=1，这满足结束条件，此时直接返回a即可。

代码实例3-2给出了一个C函数facttail，它接受一个整数n并以尾递归的形式计算n的阶乘。这个函数还接受一个参数a，a的初始值为1。facttail使用a来维护递归层次的深度，除此之外它和fact很相似。读者可以注意一下函数的具体实现和尾递归定义的相似之处。

示例3-2：以尾递归的形式计算阶乘的一个函数实现 [1] 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

/*facttail.c*/

#include"facttail.h"

/*facttail*/

int facttail(int n, int a)

{

    /*Compute a factorialina tail - recursive manner.*/

    if (n < 0)

        return 0;    

    else if (n == 0)

        return 1;    

    else if (n == 1)

        return a;

    else

        return facttail(n - 1, n * a);

}

示例3-2中的函数是尾递归的，因为对facttail的单次递归调用是函数返回前最后执行的一条语句。在facttail中碰巧最后一条语句也是对facttail的调用，但这并不是必需的。换句话说，在递归调用之后还可以有其他的语句执行，只是它们只能在递归调用没有执行时才可以执行 [1]  。

尾递归是极其重要的，不用尾递归，函数的堆栈耗用难以估量，需要保存很多中间函数的堆栈。比如f(n, sum) = f(n-1) + value(n) + sum; 会保存n个函数调用堆栈，而使用尾递归f(n, sum) = f(n-1, sum+value(n)); 这样则只保留后一个函数堆栈即可，之前的可优化删去。

注意事项:

参考代码:

#include<iostream>
using namespace std; 
typedef long long ll;
ll n,s;
ll fac(ll x,ll a)//尾递归 
{
	if(x==n)
	{
		return a;	
	}
	fac(x+1,a*(x+1));
}
int main()
{
	ll sum=0;
	cin>>n;
	s=n;
	for(ll i=1;i<=s;i++)
	{
		sum=sum+fac(1,1);
		n=i;
	} 
	cout<<sum; 
	return 0;
}