Java数据结构和算法 - 递归

2021/04/15 algorithm 共 3786 字,约 11 分钟
Bob.Zhu

递归

递归是一种方法(函数)调用自己的变成编程技术。

采用递归,是从概念上简化了问题,而不是因为它本质上更有效率。

特征

  • 调用自身
  • 当它调用自身的时候,它这样做是为了解决更小的问题
  • 存在某个足够简单的问题的层次,在这一层算法不需要调用自己就可以直接解答且返回结果

分治算法

递归的二分查找是分治算法的一个例子,吧一个大问题分成两个相对来说更小的问题,并且分别解决每一个小问题。

递归范例

三角数字

递归的triangle方法

public class TriangleApp {
  private static int theNumber;

  public static void main(String[] args) throws IOException {
    System.out.println("Enter a number: ");
    theNumber = getInt();
    int answer = triangle(theNumber);
    System.out.println("Answer: Triangle=" + answer);
  }

  public static int triangle(int n) {
    System.out.println("Entering: n=" + n);
    if (n == 1) {
      System.out.println("Returning 1");
      return 1;
    } else {
      int temp = n + triangle(n - 1);
      System.out.println("Returning " + temp);
      return temp;
    }
  }

  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);
  }
}
Enter a number: 
5
Entering: n=5
Entering: n=4
Entering: n=3
Entering: n=2
Entering: n=1
Returning 1
Returning 3
Returning 6
Returning 10
Returning 15
Answer: Triangle=15

单词字符全排序

public class AnagramApp {
  private static int size;
  private static int count;
  private static char[] arrChar = new char[100];

  public static void main(String[] args) throws IOException {
    System.out.println("Enter a word: ");
    String word = getString(); // get word
    size = word.length(); // find its size
    count = 0;
    for (int j = 0; j < size; j++) {
      arrChar[j] = word.charAt(j); // put it in array
    }
    doAnagram(size); // anagram it
  }

  /**
   * anagram [ˈænəɡræm] 相同字母异序词,易位构词,变位词
   * @param newSize
   */
  public static void doAnagram(int newSize) {
    if (newSize == 1) { // if innermost
      displayWord(); // display
      return;
    }
    for (int j = 0; j < newSize; j++) { // for each position
      doAnagram(newSize - 1); // anagram remaining
      rotate(newSize); // rotate word
    }
    System.out.print(""); // for debug
  }

  /**
   * rotate [ˈroʊteɪt] 旋转;循环
   */
  public static void rotate(int newSize) {
    int j;
    int position = size - newSize;
    char temp = arrChar[position]; // save first letter
    for (j = position + 1; j < size; j++) { // shift others left
      arrChar[j - 1] = arrChar[j]; // put first on right
    }
    arrChar[j - 1] = temp;
    System.out.print(""); // for debug
  }

  public static void displayWord() {
    if (count < 9) { // 对齐
      System.out.print(" ");
    }
    System.out.print(++count + " ");
    for (int j = 0; j < size; j++) {
      System.out.print(arrChar[j]);
    }
    System.out.flush();
    if (count % 6 == 0) {
      System.out.println();
    } else {
      System.out.print("   ");
    }
  }

  public static String getString() throws IOException {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    String s = br.readLine();
    return s;
  }
}
 1 abcd    2 abdc    3 acdb    4 acbd    5 adbc    6 adcb
 7 bcda    8 bcad    9 bdac   10 bdca   11 bacd   12 badc
13 cdab   14 cdba   15 cabd   16 cadb   17 cbda   18 cbad
19 dabc   20 dacb   21 dbca   22 dbac   23 dcab   24 dcba

递归的二分查找

public class BinarySearch {
  private int[] a; // ref to array a
  private int nElem;  // number for data items

  public BinarySearch(int max) {
    a = new int[max];
    nElem = 0;
  }

  public int size() {
    return nElem;
  }

  public int find(int key) {
    return recFind(key, 0, nElem - 1);
  }

  public int recFind(int key, int lowerBound, int upperBound) {
    int curIn = (lowerBound + upperBound) / 2;
    if (a[curIn] == key) {
      return curIn; // found it
    } else if (lowerBound > upperBound) {
      return nElem; // can't find it
    } else { // divide range
      if (a[curIn] < key) {
        return recFind(key, curIn + 1, upperBound);
      } else {
        return recFind(key, lowerBound, curIn - 1);
      }
    }
  }

  public void insert(int val) {
    int j;
    for (j = 0; j < nElem; j++) {
      if (a[j] > val) {
        break;
      }
    }
    for (int k = nElem; k > j; k--) {
      a[k] = a[k - 1];
    }
    a[j] = val;
    nElem++;
  }

  public void display() {
    for (int j = 0; j < nElem; j++) {
      System.out.print(a[j] + " ");
    }
    System.out.println();
  }
}
public class BinarySearchApp {
  public static void main(String[] args) {
    int maxSize = 100;
    BinarySearch arr = new BinarySearch(maxSize);
    arr.insert(72);
    arr.insert(90);
    arr.insert(45);
    arr.insert(126);
    arr.insert(54);
    arr.insert(99);
    arr.insert(144);
    arr.insert(27);
    arr.insert(135);
    arr.insert(81);
    arr.insert(18);
    arr.insert(108);
    arr.insert(9);
    arr.insert(117);
    arr.insert(63);
    arr.insert(36);
    arr.display();

    int key = 9;
    if (arr.find(key) != arr.size()) {
      System.out.println("Found " + key);
    } else {
      System.out.println("Can't find " + key);
    }
  }
}

文件夹遍历

参考资料

文档信息

Search

    Table of Contents