递归与分治策略（一）：推卸责任是不对的

引言：据说一群在毕达哥拉斯领导下工作的古希腊数学家，发现了数字系列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