递归的定义

       在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。

例 求n!(n为正整数) 。

 

   一般的方法：

  n! = 1*2*…*(n-1)*n

 

   递归的方法：

int factorial(int n)

    {    int x;

          if (n==0)

                x=1; 

          else

      x=factorial (n-1)*n;

          return(x); 

    }

   在该函数factorial (n)求解过程中,直接调用factorial (n-1)自身,所以它是一个直接递归函数。

递归模型

      递归模型是递归算法的抽象,它反映递归问题的递归结构,例如,前面的递归算法对应的递归模型如下：

  fun(0)=1       n=0  (1)          fun(n)=n*fun(n-1)  n>0  (2)

     其中：第一个式子给出了递归的终止条件,我们称之为递归出口；第二个式子给出了fun(n)的值与fun(n-1)的值之间的关系，我们称之为递归体。

递归算法到非递归算法的转换

      递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的；二是递归算法的时间/空间效率通常比较差。

      因此,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。

尾递归函数是以递归调用结尾的函数，是单向递归的特例。它的递归调用语句只有一个，而且是放在过程的最后。当递归调用返回时，返回到上一层递归调用语句的下一语句，而这个位置正好是程序的结尾，因此递归工作栈中可以不保存返回地址；除了返回值和引用值外，其他参数和局部变量都不再需要，因此可以不用栈，直接采用循环写出非递归过程。

　　阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后，必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数，例：

阶乘的递归求解：

int factorial(int n)

{
　　 if(n == 0) return 1;
　　 else

     {
　　　 int val = factorial(n - 1);
　　　 return n * val;
　　 }
}

转化为尾递归求解：

int factorial(int acc, int x)

 {　//acc传的值为1。
　　if(x <= 1) return acc;
　　else

     return factorial(x * acc, x - 1);
}

　　尾递归的重要性在于当进行尾递归调用时，调用者的返回位置不需要被存在调用栈里。当递归调用返回时，它直接分支到先前已保存的返回地址。因此，在支持尾递归优化的编译器上，尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量，这无疑导致了程序的可读性降低，迭代函数不像递归函数那样需要考虑函数调用的支出，而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多，而递归算法则相对迭代算法需要更多的栈空间！

把递归算法转化为非递归算法有如下三种基本方法：

      (1)通过分析，跳过分解过程，直接用循环结构的算法实现求值过程。

      (2)自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算法替代递归算法。

      (3)利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法。

 1、利用循环（迭代函数）跳过分解过程从而消除递归

       采用循环结构消除递归。求解Fibonacci数列的算法如下：

   int Fib(int n)

   {    int i,f1,f2,f3;

         if (n==1 || n==2)  return(n);

         f1=1;f2=2;

         for (i=3;i<=n;i++)

         {    f3=f1+f2;

               f1=f2;f2=f3;

         }

         return(f3);

   }

2、模拟系统的运行时栈消除递归

        下面讨论直接使用栈保存中间结果,从而将递归算法转化为非递归算法的过程。

仍以例6.1的递归算法进行讨论

fun(0)=1       n=0  (1)          fun(n)  =   n*fun(n-1)     n>0  (2)

,其递归模型有一个递归出口和一个递归体两个式子,分别称为(1)式和(2)式。设计一个栈,其结构如下：

   struct

   {  int vn;   

  int vf;   

  int tag; 

   } St[MaxSize]; 

计算fun1(5)之值的过程如下：

将(5,*,1)进栈;

while (栈不空)

{    if (栈顶元素未计算出栈顶元素的vf值即St[top].tag==1)

     {     if (栈顶元素满足(1)式)

      求出对应的St[top].vf值,并置St[top].tag=0;

                表示已求出对应的函数值;

  else 

      将(St[top].vn-1,*,1)进栈;

    }

    else if (栈顶元素已计算出栈顶元素的vf值即St[top].tag==0)

          显然栈顶元素由次栈顶元素通过(2)式分解得到的,回过来

          由栈顶元素的vf值计算出次栈顶元素的vf值并退栈;

    if  (栈中只有一个已求出vf值的元素)

        退出循环;

}

St[0].vf即为所求的fun1(n)值;

对应的非递归fun1算法如下：

  int fun1(int n)

  {     top++;       

        St[top].vn=n; St[top].tag=1;

        while (top>-1)       

        {           if (St[top].tag==1)   

          {     if (St[top].vn==0) 

    {     St[top].vf=1;

          St[top].tag=0;

    }

    else 

    {    top++;

          St[top].vn=St[top-1].vn-1; St[top].tag=1;

    }

          }

else if (St[top].tag==0)     

              {    St[top-1].vf=St[top-1].vn*St[top].vf; 

        St[top-1].tag=0;

        top--;

                }

 

                        if (top==0 && St[top].tag==0)

      break;

  }

  return(St[top].vf);

    }