编程小技巧

        今天跟大家分享的小技巧是关于递归问题的。我们先来看这样一道数学题：编程程序求S的值

        这是我在做面试时给求职者出的一道笔试题，很可惜，多数人的答案并不好。我们先来看看他们的分析过程和编写的程序。首先对问题进行分析：

        多数人想到了如何编写程序，无非就是一个双循环问题，于是编写程序如下：

int n  = 5;
long s = 0;
for (int i = 1; i <= n; i++)
{
        long f = 1;
        for (int j = 1; j <= i; j++)
        {
                f *= j;
        }
        s += f; 
}
printf("%ld\n", s);

        程序的运行结果是正确的，但逻辑上还不够清晰。为什么这么说呢？我们来看看关于阶乘的数学定义：

        可以看到，阶乘的数学定义就是递归的定义，也就是说n的阶乘等于n乘以n-1的阶乘，1的阶乘为1。再来看看累加和的数学定义：

        与阶乘的定义类似，累加和的数学定义也可以归纳为一个递归定义，即：n的1到k的累加和等于n加上n的1到k-1的累加和，k等于1时，累加和为n。

        跟数学定义保持一致，我们定义两个递归函数如下：

long fa(long n)
{
        if (n == 1)
        {
                return 1;
        }
        return n * fa(n - 1);
}
long fs(long n)
{
        if (n == 1)
        {
                return fa(n);
        }
        return fa(n) + fs(n - 1);
}

        有的朋友会问直接用循环的方式实现不是也很简单吗？仔细分析上述算法不难看出，递归的引入简化了程序设计的问题，划分了不现的关注层次，使思考的关注点定位在设计上。而用循环不不仅掩盖了问题的本质，还需要分散精力去考虑数组下标增减等细节问题。使用递归方式来解决这一类本来就是递归定义的问题，会使的程序简洁明了，逻辑清晰，又便于维护与修改。

        最后请大家思考这样两个问题：

        1.如果n的值很大，比如n=1000,程序应该如何处理？

        2.很多朋友对递归很是抵触，觉得递归的执行效率没有循环高，那么为什么递归的效率会比循环低呢？低在什么地方？时间复杂度和空间复杂度究竟是多少？

        今天的小技巧你学会了吗？