昨天去公司面试，有个题目叫：用递归算100的阶层，想了好久！！！ 用最简单的求阶层函数来举例：n! = n*(n-1)*(n-2)***2*1常见的递归实现如下：int fun(int n){ if( n<=1 ) return 1; return n*fun(n-1);}不用多说，这个实现下每次递归调用都会在当前层的工作记录中分配一个4字节（IBM兼容机）的空间来存放n的值。若栈的深度为DEPTH，那么一共需要DEPTH×4个字节存放参数。那么能不能避免这些存储空间呢，我们来看看引用的情况：int fun(int &n){ if( n<=1 ) return 1; return n*fun(n-1);}这段代码编译不能通过，原因是n-1只是一个右值。这里简单介绍一下c＋＋中的无名对象（变量）。c＋＋中的无名对象与const常量有些相似，他们都只能做右值而不能做左值，区别是const常量是有地址的可以取地址，而无名对象一般是不可以的。这里n－1有点无名对象的味道，因为fun要求一个变量引用。由于n－1是右值，所以把参数类型改成int fun(const int & n)就可以了。int fun(const int &n){ if( n<=1 ) return 1; return n*fun(n-1);}现在运行通过了，但是栈空间需求仍然没有减少，因为引用的是无名对象，无名对象只是寄存器中的一个值，是没有RAM地址的。所以每递归调用一次，就会在工作记录中分配空间来存放n－1，实际效果相当于const int n = n-1;那么换个思路。以上程序之所以如此是因为传给递归函数的不是n本身，现设计如下：int fun(const int & n){ cout<<(long)&n<<endl; if( n<=1 ) return 1; --n; return (n+1)*fun(n);
