首页 > 代码库 > C程序设计的抽象思维-递归入门

C程序设计的抽象思维-递归入门

【斐波那契序列】

序列中的每一个新项都是它前两项的和。

      0    1     1     2     3      5      8       13       21       34      55       89       144  …………

数学表达式表示序列中的一个新项:   tN = tN-1 +  tN-2

像这种类型的表达式,序列中的每一个元素都是由先前的元素来确定,这种序列称为递归关系

     斐波那契序列的完整定义如下:

         tn =  n       n= 0 或者 n= 1 

         tn = tn-1 + tn-2  n为其他值

 这个数学公式是一个递归实现函数Fib(n)的理想模型。

int Fib(int n)
{
	if(n<2){
		return (n);
	}else{
		return (Fib(n-1) + Fib(n-2));
	}
}

Fib(5)的计算步骤


显然这个递归的分解产生了许多冗余的调用,在这些调用中,计算机若干次调用了相同的项。

【改进】

斐波那契序列并不是唯一的通过下面的递归关系决定各项的序列:

       tn = tn-1 + tn-2

按照对初始两项的选择,可以产生许多不同的序列,传统的斐波那契序列如下:

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……

它定义t0 = 0 ,t1 = 1。然而,如果定义t0 = 3和t1 = 7,将会得到下面的序列:

   3, 7, 10, 17, 27, 44, 71, 115, 186, 301, 487, 788, 1275,……

这些序列全都采用相似的递归关系,它规定了每一个新项都是它的前两项的和。这些序列唯一的区别是初始两项的选择。通常,将符合这种样式的序列称为加法序列

加法序列的概念使得找到斐波那契序列的第n项的问题转变为了一个更普遍的崽一个初始化为t0和t1的加法序列中找到第n项的问题。这个函数要求三个参数

int AdditiveSequence(int n, int t0, int t1);
采用这个函数,很容易就实现了Fib。

int Fib(int n)
{
	return (AdditiveSequence(n, 0, 1));
}

下一步就是如何实现AdditiveSequence函数。

假设希望在初始项为3 和7 的一个加法序列中找到t6.

    t0        t1      t2    t3     t4    t5       t6     t7     t8    t9

     3        7     10    17    27   44   71    115 186  301……

 可以看到t6 = 71。我们发现t6其实就是在以7和10开头的加法序列中的t5

    t0        t1      t2    t3     t4    t5       t6     t7     t8

    7        10    17    27   44   71    115 186  301……

根据这一点我们可以递归实现AdditiveSequence函数。

int AdditiveSequence(int n, int t0, int t1)
{
	if(n == 0) return (t0);
	if(n == 1) return (t1);
	return (AdditiveSequence(n - 1, t1, t0 + t1));
}

Fib(5)的计算过程

       Fib(5)

            =  AdditiveSequence(5, 0 , 1)

               = AdditiveSequence(4, 1, 1)

                   = AdditiveSequence(3, 1, 2)

                      = AdditiveSequence(2, 2, 3)

                         = AdditiveSequence(1, 3, 5)

                             = 5

明显这个实现方法的递归效率大于前一种。