首页 > 代码库 > 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
明显这个实现方法的递归效率大于前一种。