递归函数

学C数据结构时在讲栈的章节里重点提到递归函数的思想，现在我在看java时同样遇到递归的思想，所以就想整理整理一下自己的“笔记”，理一下自己的思路。

递归的定义：递归是指在定义自身的同时又出现了对自身的调用。 如果一个函数在其定义体内直接调用自己，则称其为直接递归函数； 如果一个函数经过一系列的中间调用语句，通过其它函数间接调用自己，则称其为间接递归函数。  见名思意，递归实际上是递推与回归的结合。

下面见一个例子，这个例子很有意思，因为在我考数据结构时且好出了这道题，我刚好在考试前复习时见道同样的题，然后我并且在考试前运行过此题目的程序。题目是：求函数F＝1+1/2+1/3+……+1/n的递归出口和递归体。

在这里先提一下递归模型：

递归模型：
    由递归体与递归出口组成
{
      if(递归出口)
             (简单操作);
     else
             (递归体);
}

根据题目写的c程序如下：

/*****************************************
求函数F＝1+1/2+1/3+……+1/n
运行环境：Turbo 2.0&&Turbo C for Windows
Firedy
2007-1-8
******************************************/

float fun(int n)    /*递归函数*/
{
            /*float k=1.0/n;*/
       if(n==1)         /*递归出口*/
             return 1;   
       else
             return fun(n-1)+1.0/n;/*k+=fun(n-1);*/  /*递归体*/
}

main()
{
      int n;
      float F;
      printf("F=1+1/2+1/3+...+1/n=?\n");
      printf("\ninput n(n!=0):");
      scanf("%d",&n);
      F=fun(n);
      printf("\nF=%.3f",F);
}

运行结果：

再看个java递归函数：

//利用递归求10！

class Factor11
{
        static long Fact(int n)
        {
                if(n==1)        //递归出口
                        return 1; //简单操作
                else
                        return n*Fact(n-1);     //递归体
        }

        public static void main(String args[])
        {
                int n=10;
                System.out.println(n+"!="+Fact(n));
        }
}

运行结果为：

 

从中可以看出递归的优点，接着说下教材里（我使用的c数据结构教材是西电科大出版的耿国华等编著的《数据结构－－C语言描述》）提到的递归算法到递归算法的转换：

递归算法有两个特性：（1）递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是有效的。  （2）递归算法的时间效率底。（计算机编程很讲究算法的效率问题，也许所以就有了需要消除递归的原因，对这方面的理解，我没有怎么去思考，毕竟目前我们为了完成题目，首先是找思维直观，容易想到的方法，而对于效率的或效益的问题，更多的是企业或更进一步的研究学习是应该很重视的一个问题，可能这也可以说是我们学校的教育与社会之间的差距吧。）

其实，一个问题的思考，可以延伸到很多领域，研究研究是永无止境的