《Java软件结构：设计和使用数据结构（第2版）》读书笔记1－递归

《Java软件结构：设计和使用数据结构（第2版）》读书笔记1－递归

  大学的数据结构和算法根本就是混过来的，某天在某某论坛里有个关于数据结构和算法到底在日常的编程到底有多大的用处。对于我来说，我并不觉得我用上了那些讲的数据结构和算法。Java Collection Framework已经跟我们做了这些。我已经能非常熟练的使用Collection里面的类库。但是我们用的基本上都是那些线性集合（堆栈，队列，列表，Set），非线性集合（树，堆，散列和图）我感觉比较少用到。我也主要是想对非线性集合做一些比较。线性集合比较简单。

 

  第一章到第九章都是讲线性集合， 也比较容易理解， 在这里就忽略掉。第十章是讲递归算法。我对这章比较感兴趣，用递归实现某个算法真的感觉非常优雅，代码短而少，许多非线性集合都是用递归来实现的。但也有他的缺点， 对方法的每次递归调用都会生成新的局部变量和局部参数。假如递归层次太多的话，就会消耗太多的stack。

 

任何递归定义都必须有一个非递归部分；这个非递归部分叫做基本情况，它使的递归跳出无穷循环递归。

Ex 1： 1~N的累加过程，数值1～N的累加可以看成是1～N<spanstyle="font-family:宋体">－1的累加加上N。

 

       public int sum(int num){

              int result = 0;

              if (num == 1){

                     return 1;

              }

              return result + num + sum(num - 1);

       }

这里的基本情况就是但num＝＝1的时候。 当然这个可以不用递归来处理，用一个for就行了（而且比用递归更直观）。我们必须能判断什么时候使用递归，什么时候不使用递归，所有问题都可以使用迭代（for循环）解决问题。不过有些情况下，迭代方式过于复杂，对某些问题，递归可以写出短小而优雅的代码。

 

直接递归和间接递归，方法调用自己，这就是直接递归（如上个例子）。方法调用另一个方法，最终导致再调用原方法。这就是间接递归。

 

河内塔问题（Towers of Hanoi）（可以上网找找这个经典问题的描述）

规则：

l         一次只能移动一张圆盘

l         不能将大盘放在小盘的上方

l         除了那张在柱子之间搬动的圆盘之外，所有圆盘都必须在某根柱子上

 

策略：

l         将最上方的N－1张圆盘从最初的柱子移到那根多处的柱子上

l         将最大的圆盘从最初的柱子移动到最终的柱子上

l         再将那个多出柱子上的N－1张圆盘移到最终的柱子上

 

Code：

public      class TowersOfHanoi{

              private int totalDisks;

              // ------------------------------------------------------

              // Sets up the puzzle with the specified number of disks

              // ------------------------------------------------------

              public TowersOfHanoi(int disks){

                     this.totalDisks = disks;

              }

              // ----------------------------------------------------------

              // Performs the initial call to moveTower to solve the puzzle.

              // Moves the disks from tower 1 to tower 3 using tower 2

              // ----------------------------------------------------------

              public void solve(){

                     moveTower(totalDisks, 1, 3,2);

              }

              // -----------------------------------------------------------------

              // Moves the specified number of disks from one tower to another by 

              // moving a subtower of n-1 disks out of the way, moving one disk, 

              // then moving the subtower back, Base case of 1 disk.

              // -----------------------------------------------------------------

              private void moveTower(int numDisks, int start, int end, int temp) {

                     if (numDisks == 1){

                            moveOneDisk(start, end);

                     }else{

                            moveTower(numDisks-1, start, temp, end);

                            moveOneDisk(start, end);

                            moveTower(numDisks-1, temp, end, start);

                     }

              }

              private void moveOneDisk(int start, int end) {

                     System.out.println("Move one disk from " + start + " to " + end);

              }

       }