递归
递归是一种方法(函数)调用自己的编程技术。
1.三角数字
1,3,6,10,15,21，...
使用递归查找第N项是几
// triangle.java// evaluates triangular numbers// to run this program: C>java TriangleAppimport java.io.*;class TriangleApp { static int theNumber; public static void main(String[] args) throws IOException { System.out.print("Enter a number: "); theNumber = getInt(); int theAnswer = triangle(theNumber); System.out.println("Triangle="+theAnswer); } // end main()//------------------------------------------------------------- public static int triangle(int n) { if(n==1) return 1; else return ( n + triangle(n-1) ); }//------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; }//------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); }//-------------------------------------------------------------- } // end class TriangleApp 2.变位字
变位字实际上就是高中学的排列，几个不同的字母共有几种不同的排列方法。如a.b.c共有8中排列方法。下面是其算法，该算法打印的结果是所有的排列结果。
// anagram.java// creates anagrams// to run this program: C>java AnagramAppimport java.io.*;class AnagramApp { static int size; static int count; static char[] arrChar = new char[100]; //----------------------------------------------------------- public static void main(String[] args) throws IOException { System.out.print("Enter a word: "); // get word String input = getString(); size = input.length(); // find its size count = 0; for(int j=0; j 3.递归的二分法查找
二分法查找效率高，因为它总是用最少的次数查到想要的值。
// binarySearch.java// demonstrates recursive binary search// to run this program: C>java BinarySearchAppclass ordArray { private long[] a; // ref to array a private int nElems; // number of data items //----------------------------------------------------------- public ordArray(int max) // constructor { a = new long[max]; // create array nElems = 0; } //----------------------------------------------------------- public int size() { return nElems; } //----------------------------------------------------------- public int find(long searchKey) { return recFind(searchKey, 0, nElems-1); } //----------------------------------------------------------- private int recFind(long searchKey, int lowerBound, int upperBound) { int curIn; curIn = (lowerBound + upperBound ) / 2; if(a[curIn]==searchKey) return curIn; // found it else if(lowerBound > upperBound) return nElems; // can't find it else // divide range { if(a[curIn] < searchKey) // it's in upper half return recFind(searchKey, curIn+1, upperBound); else // it's in lower half return recFind(searchKey, lowerBound, curIn-1); } // end else divide range } // end recFind() //----------------------------------------------------------- public void insert(long value) // put element into array { int j; for(j=0; j value) // (linear search) break; for(int k=nElems; k>j; k--) // move bigger ones up a[k] = a[k-1]; a[j] = value; // insert it nElems++; // increment size } // end insert() //----------------------------------------------------------- public void display() // displays array contents { for(int j=0; j 4.汉诺塔问题(Hanoi)
这是个经典的游戏，下面的A、B、C分别代表左、中、右的三根柱子，1、2、3分别代表从上往下也就是从小到大的盘子。
// towers.java// solves Towers of Hanoi puzzle// to run this program: C>java TowersAppclass TowersApp { static int nDisks = 3; public static void main(String[] args) { doTowers(nDisks, 'A', 'B', 'C'); } //----------------------------------------------------------- public static void doTowers(int topN, char src, char inter, char dest) { if(topN==1) System.out.println("Disk 1 from " + src + " to "+ dest); else { doTowers(topN-1, src, dest, inter); // src to inter System.out.println("Disk " + topN + // move bottom " from " + src + " to "+ dest); doTowers(topN-1, inter, src, dest); // inter to dest } }//------------------------------------------------------------- } // end class TowersApp 5.归并排序
归并排序的效率要高于简单排序(冒泡、选择和插入排序)，简单排序时间复杂度都是O(N2),而归并只需要O(N*logN)，归并排序的一个缺点是它需要在存储器中有另一个大小等于被排序的数据项树木的数组，如果初始数组几乎占满整个存储器，那么归并排序将不能工作，但是如果有足够的空间，归并排序会是一个很好的选择。
下面是一个执行归并排序的java程序，它并不是递归程序，只是为了理解归并排序的插曲。
// merge.java// demonstrates merging two arrays into a third// to run this program: C>java MergeAppclass MergeApp { public static void main(String[] args) { int[] arrayA = {23, 47, 81, 95}; int[] arrayB = {7, 14, 39, 55, 62, 74}; int[] arrayC = new int[10]; merge(arrayA, 4, arrayB, 6, arrayC); display(arrayC, 10); } // end main() //----------------------------------------------------------- // merge A and B into C public static void merge( int[] arrayA, int sizeA, int[] arrayB, int sizeB, int[] arrayC ) { int aDex=0, bDex=0, cDex=0; while(aDex < sizeA && bDex < sizeB) // neither array empty if( arrayA[aDex] < arrayB[bDex] ) arrayC[cDex++] = arrayA[aDex++]; else arrayC[cDex++] = arrayB[bDex++]; while(aDex < sizeA) // arrayB is empty, arrayC[cDex++] = arrayA[aDex++]; // but arrayA isn't while(bDex < sizeB) // arrayA is empty, arrayC[cDex++] = arrayB[bDex++]; // but arrayB isn't } // end merge() //----------------------------------------------------------- // display array public static void display(int[] theArray, int size) { for(int j=0; j 使用了递归的归并排序完整版。
// mergeSort.java// demonstrates recursive merge sort// to run this program: C>java MergeSortAppclass DArray { private long[] theArray; // ref to array theArray private int nElems; // number of data items //----------------------------------------------------------- public DArray(int max) // constructor { theArray = new long[max]; // create array nElems = 0; } //----------------------------------------------------------- public void insert(long value) // put element into array { theArray[nElems] = value; // insert it nElems++; // increment size } //----------------------------------------------------------- public void display() // displays array contents { for(int j=0; j 6.消除递归
有一些算法趋向于用递归的方法，另一些则不是，其实递归的效率并不高，人们用他们只是他们更加简洁，所以有时候需要把递归的算法转换成非递归的，这种转换经常会用到栈。
事实上，大部分的编译器都是使用栈来实现递归的，当调用一个方法的时候，编译器会把这个方法的所有参数及返回地址(这个方法返回时控制到达的地方)都压入栈，然后把控制转移给这个方法，当这个方法返回的时候，这些值退栈，参数消失了，并且控制权重新回到返回地址处。
下面是一个转换的算法，实现的是前面的triangle.java，三角数字。
// stackTriangle.java// evaluates triangular numbers, stack replaces recursion// to run this program: C>java StackTriangleAppimport java.io.*; // for I/Oclass Params // parameters to save on stack { public int n; public int returnAddress; public Params(int nn, int ra) { n=nn; returnAddress=ra; } } // end class Paramsclass StackX { private int maxSize; // size of StackX array private Params[] stackArray; private int top; // top of stack//-------------------------------------------------------------- public StackX(int s) // constructor { maxSize = s; // set array size stackArray = new Params[maxSize]; // create array top = -1; // no items yet }//-------------------------------------------------------------- public void push(Params p) // put item on top of stack { stackArray[++top] = p; // increment top, insert item }//-------------------------------------------------------------- public Params pop() // take item from top of stack { return stackArray[top--]; // access item, decrement top }//-------------------------------------------------------------- public Params peek() // peek at top of stack { return stackArray[top]; }//-------------------------------------------------------------- } // end class StackXclass StackTriangleApp { static int theNumber; static int theAnswer; static StackX theStack; static int codePart; static Params theseParams;//------------------------------------------------------------- public static void main(String[] args) throws IOException { System.out.print("Enter a number: "); theNumber = getInt(); recTriangle(); System.out.println("Triangle="+theAnswer); } // end main()//------------------------------------------------------------- public static void recTriangle() { theStack = new StackX(10000); codePart = 1; while( step() == false) // call step() until it's true ; // null statement }//------------------------------------------------------------- public static boolean step() { switch(codePart) { case 1: // initial call theseParams = new Params(theNumber, 6); theStack.push(theseParams); codePart = 2; break; case 2: // method entry theseParams = theStack.peek(); if(theseParams.n == 1) // test { theAnswer = 1; codePart = 5; // exit } else codePart = 3; // recursive call break; case 3: // method call Params newParams = new Params(theseParams.n - 1, 4); theStack.push(newParams); codePart = 2; // go enter method break; case 4: // calculation theseParams = theStack.peek(); theAnswer = theAnswer + theseParams.n; codePart = 5; break; case 5: // method exit theseParams = theStack.peek(); codePart = theseParams.returnAddress; // (4 or 6) theStack.pop(); break; case 6: // return point return true; } // end switch return false; } // end triangle//------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; }//------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); }//-------------------------------------------------------------- } // end class StackTriangleApp 以上算法多少是系统的把一个递归程序转换成了使用栈的程序，这表明对于任意一个递归程序都有可能做出这种转换，然而在实践中，我们从一开始就不往递归想，所以一开始就用基于栈的方法，而不是从递归转换，这样就可以精简上面的程序，去掉了swith语句，使代码更有效率。
以下是更有效率的代码。
// stackTriangle2.java// evaluates triangular numbers, stack replaces recursion// to run this program: C>java StackTriangle2Appimport java.io.*; // for I/Oclass StackX { private int maxSize; // size of stack array private int[] stackArray; private int top; // top of stack//-------------------------------------------------------------- public StackX(int s) // constructor { maxSize = s; stackArray = new int[maxSize]; top = -1; }//-------------------------------------------------------------- public void push(int p) // put item on top of stack { stackArray[++top] = p; }//-------------------------------------------------------------- public int pop() // take item from top of stack { return stackArray[top--]; }//-------------------------------------------------------------- public int peek() // peek at top of stack { return stackArray[top]; }//-------------------------------------------------------------- public boolean isEmpty() // true if stack is empty { return (top == -1); }//-------------------------------------------------------------- } // end class StackXclass StackTriangle2App { static int theNumber; static int theAnswer; static StackX theStack; public static void main(String[] args) throws IOException { System.out.print("Enter a number: "); System.out.flush(); theNumber = getInt(); stackTriangle(); System.out.println("Triangle="+theAnswer); } // end main()//------------------------------------------------------------- public static void stackTriangle() { theStack = new StackX(10000); // make a stack theAnswer = 0; // initialize answer while(theNumber > 0) // until n is 1, { theStack.push(theNumber); // push value --theNumber; // decrement value } while( !theStack.isEmpty() ) // until stack empty, { int newN = theStack.pop(); // pop value, theAnswer += newN; // add to answer } }//------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; }//------------------------------------------------------------- public static int getInt() throws IOException { String s = getString(); return Integer.parseInt(s); }//-------------------------------------------------------------- } // end class StackTriangle2App 总之，递归能简化代码，但是逻辑上比较复杂，效率也并不高。