第十四讲 递归函数

       上两讲我们说到函数,不过说实在的,对于非专业讲师来说,这个主题真的没啥好讲的,所以我讲没劲,大家也看得没劲,不过还好,我们今天进入下一个话题,今天要说的是递归函数,递归函数可以归为函数一类,同时也归为算法一类,他也是数据结构的一类,虽然我们现在不讨论数据结构,但这里既然说到函数,就拿出来说一下吧,顺便大家也好对这个递归函数有所理解。
大家还记得我们第十一讲里面有一个关于计算幂次方的简单函数吗?我们当时是使用一个while循环来完成这个简单的算法,这个算法确实是最简单的,同时也是最好用的,等以后我们使用模板函数来模板化的时候我们还是会用这个算法,不过今天既然我们说到递归,我们是不是可以用递归函数来实现这个功能呢?当然可以,在说递归思想之前我们先来看我们对幂次方算法的重新实现,如果大家看完这个实现之后明白递归思想了的话我也就懒得多说了,哈哈,偷懒啊。
———————————-
我们先用循环来实现,顺便让大家回忆一下
int power(const
int n,int m)

{
     
int s=1;


      while(m–)
           s *= n;


      

return s;


}
下面我们用递归来实现
int power(const
int n,int m)

{
     
int s;


      if(m>0)
           s = n*power(n,m-1);


      else 
           s = 1;


      
return s;


}
———————————
两种实现方法,大家看出了端倪了吗?相信聪明的你们已经看出来了,用递归简直是多此一举啊,不错,在这个实现里面,用递归确实不是明知之举,但不可否认递归思想也是一种算法思想,我们来验证一下吧:
第十四讲 递归函数
再我们常用的范围内使用完全没问题,不过这样实现太过麻烦了,现在我们再来看看下面这个实现:
———————————-
void  to_binary (unsigned long n)  
{
int r;

r = n % 2;

if (n >= 2)
to_binary(n/2);

putchar(‘0’+r);

return;

}
—————————————
相信大家已经知道这个函数实现的功能了,这就是将一个十进制数转换为二进制数的实现,所以说到底,这是一个递归的反向计算的思想,很有意思,在要实现反向计算的时候,递归却又比循环好用得多,还是老规矩,我们来验证一下结果:
第十四讲 递归函数
关于递归的好和递归的坏都在这两个例子里得到证明,所以该什么时候使用递归就看大家的想法了,有人说,不管是C还是C++或者是JAVA又或者是C#他们不过都只是工具而已,数据结构才是衡量一个程序员功力深浅的标准,而算法又是一门仁者见仁智者见智的东西,但是在计算机面前似乎又有一个标准,相信大家之所以选择学习C/C++就是因为看上他的效率,所以算法之重要也就不言而喻了,今天我们所说的递归只是其中的一类,后面我们还会说一些基本的算法思想链表和队列,二叉树和容器。
还是回到递归函数上面来吧,现在我们来说说递归的基本原理:
递归,简单点说,就是每次循环都是调用自己,相信每位都对数列不陌生,在数列里面大家是不是经常有a[n] = a[n-1]XX等关系式,其实递归也就是解决这类问题的。
递归函数有六个要点:
第一,每一级的函数调用都有自己的变量(如果不理解,再回头去看看我们上面的两个例子)
       第二,每一次函数调用都会有一次返回。
       第三,递归函数中,位于递归调用前的语句和各级被调函数具有相同的执行顺序。
       第四,递归函数中,位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反。
       第五,虽然每一级递归都有自己的变量,但是函数并不会得到复制。
       第六,递归函数中必须包含可以终止递归调用的语句。
对于第三和第四,如果还有不解的没关系,我们再来看看下面的例子。
———————————-

void test(int n)
{
printf (“第 %d : %dn”,n,n);

 
     if (n <4)
test(n + 1);

printf (“第 %d : %dn”,n,n);

 
}
————————————-
我们我们用个main()来驱动这个函数,看看输出的情况会是什么。
—————————–
int main()
{
      test(1);


      system(“PAUSE”);


     

return 0;


}
——————————
再我们打印结果之前,大家再回头去第三第四条吧,好对我们下面的输出不会觉得怪异:
第十四讲 递归函数
现在对递归是不是有些理解了呢?
斐波纳契列定义这是一个面试考试高频出现的考题,现在我们用递归来实现这个定义:第一个和第二个数字都是 1 ,而后续的每个数字是其两个数字之和。
———————————–
int Fibonacci (int n)
{
if (n >2)

return Fibonacci (n-1) + Fibloacct (n-2);

else

return 1;

}
————————————-
很简单,我就不截图了,这是一个将递归的优点发挥到极限的例子,最后,总结一下递归的优缺点然后就结束今天的内容吧:
优点在于为某些编程问题提供了最简单的解决方法,而缺点是一些递归算法会很快耗尽计算机的内存资源。同时,使用递归的程序难于阅读和维护。还是上面那句话,怎么使用就看大家怎么看了。

发表评论