编程小技巧

    返回首页    发表留言
本文作者:李德强
          技巧六:递归
 
 

        今天跟大家分享的小技巧是关于递归问题的。我们先来看这样一道数学题:编程程序求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.很多朋友对递归很是抵触,觉得递归的执行效率没有循环高,那么为什么递归的效率会比循环低呢?低在什么地方?时间复杂度和空间复杂度究竟是多少?

 

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

 

    返回首页    返回顶部
  看不清?点击刷新

 

  Copyright © 2015-2018 问渠网 辽ICP备15013245号