`

递归与分治策略(一):推卸责任是不对的

阅读更多

引言:据说一群在毕达哥拉斯领导下工作的古希腊数学家,发现了数字系列1,3,6,10,15,21...
中有一种奇特的联系。你能知道这个数字的系列的下一个数字是什么吗?
给你一点思考的时间,在这里停下来得出你自己的想法并验证你的结论,别往下偷看哦。

当我看到这个数字系列时我想起了中学时找通项公式的方法:
(你可以先采用归纳法,不一定一次就能找出来,贵在参与。。。)

第一项的值为初始值: n=1,f(1)=1;
第二项的值:        n=2,f(2)=f(1)+2=1+2=3;
第三项的值:        n=3,f(3)=f(2)+3=3+3=6;(靠谱O(∩_∩)O~)
第四项的值:        n=4,f(4)=f(3)+4=6+4=10;(靠谱,不过继续)
第五项的值:        n=5,f(5)=f(4)+5=10+5=15;
..........
..........
第N项的值:         n=n,f(n)=f(n-1)+n;

基本上已经找出规律来了吧,你也可以采用数学归纳法来证明一下你的结论,说到这里,真有点怀念中学时代啊。
不过我想大多数人都不会那么去做?
How to do?Let computer just do it!

A.用循环证实你的想法:

public int triangle(int n){

 int total=0;
 while(n>0)       //直到n=0
   {
   total=total+n;
   --n;
   }
   return total;
}
这个循环一直做了n次,直到n=0时exit

B.使用递归查找第N的值:
递归用一种形象的说法,就是推卸责任给别人,比如说,Marry问你道小学数学题,她很高兴地拿着
漫画版数学课本来问你:“哥哥,n=1,f(1)=1...,n=8,f(8)=f(7)+8;n=9,f(9)=?"
而你说:"Marry,你告诉我f(8)的值,我就告诉你f(9)的值。。。"
结果Marry就哭着去告诉妈妈说我欺负他。

妈妈过来看见我正在玩游戏,有点不高兴,于是我赶快用计算机给她算了算,并偷偷对Marry说:
What is f(9)?Let computer just do it and tell us!

其实我什么也没做,这一切全是Marry以及出这道题的人告诉你的答案!

public int triangle(int n){
  return (n + triangle(n-1));
}

在计算机里运行一下你也许会发现一个问题,就是它并没有给你返回一个结果,而是无限的循环下去。。。
没有答案,怎么办?

推卸责任是不对的...

How to do?

C.不推卸责任:

为了防止无限重复推卸责任,使你的计算机陷于无法自拔的境地,你只需要找到JUST one!
也就是当n=1的时候,f(1)=1是知道的,你仅仅要做的就是找到f(1)帮你解围,而不是无限的推卸责任和扯皮!
所以推卸责任到此为止,STOP here!

public int triangle(int n){
  if(n==1)
    return 1;
  else
    return (n + triangle(n-1));
}

说明:每一个递归方法都有一个基值(终止)条件,此时我们称为基值情况。

上面就是我们经常遇到的三角数字的应用。

D.总结一下递归方法特征:

(1)调用自身。
(2)当它调用自身的时候,它这样做是为了解决更小的问题,这也是一种分治策略。
(3)总存在某个足够简单的问题的层次,在这一层算法不需要推卸责任就可以直接解答且返回结果。

E.递归方法有效率吗?
递归就是程序设计中的数学归纳法。
人们掌握了递归方法之后,常常采用递归,是因为它从概念上简化了问题,它采取分治的策略,使规模化小,
从而变得更加简单,而不是因为本质上更有效率。
这个方法的大规模调用,对CPU和内存都有额外的开销。它需要在系统内存空间存储所有的中间参数以及返回值,
如果大量的数据需要存储,就会引起栈溢出的问题。当大规模自身方法调用时可考虑消除递归。
下回将讨论这个问题,以及汉诺塔问题,递归的二分查找,变位字的全排列问题。。。Sleeping

分享到:
评论
3 楼 rink1969 2009-12-15  
原始递归
极小化运算
广义单元函数
2 楼 Trustno1 2009-12-15  
其实这个数列放在这里做讲解递归的Sample是大材小用了.这个数列经过推广后,是一个极其重要的数学结果.在并行计算里面,没有这个数列几乎80%的并行算法是无解的,所以以前很多Vector Process里面把它做成了一个Primitive Operation.

1 楼 kimmking 2009-12-15  
n(n+1)/2

相关推荐

Global site tag (gtag.js) - Google Analytics