数据结构之递归

 

　　在这篇文章里，我们主要讨论和递归相关的话题。递归是数据结构中解决复杂问题时非常有效的一种思考方式，对于一个复杂的问题，我们可以从中抽取一个可以通过迭代方式解决的子问题，而子问题是一个容易解决的问题。在使用递归时，有两个问题需要注意：1）抽取递归体；2）确定递归边界条件以及处理方式。

　　下面我们来看相关的题目。

• 斐波那契数列
  我想这应该是最常见的递归的例子了，我们可以使用递归和非递归两种方式来实现它。
  首先来看非递归的方式：
  

  public static int fibo2(int n)
  {
      if (n < 0) return -1;
      if (n == 0) return 0;
      
      int a = 0,b = 1,c;
      for (int i = 2; i <= n; i++)
      {
          c = a + b;
          a = b;
          b = c;
      }
      return b;
  }

  接着是使用递归方式：

  public static int fibo1(int n)
  {
      if (n < 0) return -1;
      if (n == 0) return 0;
      if (n == 1) return 1;
      return fibo1(n - 1) + fibo1(n - 2);
  }

• 对于一个N*N的矩阵，从左上角开始遍历，每次只能横着走或者竖着走，问一共有多少种方式可以到达矩阵的右下角。
  思路：可以把矩阵看成是N行N列的数据结构，初始时，对角线距离为N行、N列，当走一步之后，距离变为（N行、N-1列）或者是（N-1行、N列），直到距离变为（0行、0列）后，表明已经走到了右下角。
  

  public static void printAllPath(int n)
  {
      int[][] matrix = Matrix.initMatrix(n, 50);
      Matrix.printMatrix(matrix);
      ArrayList<Integer> path = new ArrayList<Integer>();
      walk(matrix, n, 0, 0, path);
  }
  
  private static void walk(int[][] matrix, int n, int row, int column, ArrayList<Integer> path)
  {
      path.add(matrix[row][column]);
      if (row == n - 1 && column == n -1)
      {
          StringBuffer sb = new StringBuffer();
          for(int value : path) sb.append(value).append("->");
          System.out.println(sb.substring(0, sb.length() - 2));
      }
      if (row < n -1)
      {
          ArrayList<Integer> path1 = (ArrayList<Integer>)path.clone();
          walk(matrix, n, row + 1, column, path1);
      }
      if (column < n - 1)
      {
          ArrayList<Integer> path2 = (ArrayList<Integer>)path.clone();
          walk(matrix, n, row, column + 1, path2);
      }
  }

  执行结果（首先生成一个矩阵，然后列出各种可能方式）

  22    17    35    
  16    3    38    
  46    39    4    
  
  22->16->46->39->4
  22->16->3->39->4
  22->16->3->38->4
  22->17->3->39->4
  22->17->3->38->4
  22->17->35->38->4

• 列出给定集合的所有子集
  思路：按照子集的定义，对于长度为N的集合来说，它的子集长度是从1到N-1，我们可以先假设求长度为M的子集，那应该怎么做呢？首先可以循环遍历集合，取出某一个元素，然后计算除去该元素的集合的长度为M-1的子集，然后递归，直到最后要找长度为1的子集为止。
  然后按照上述思路，将M从1开始一直设置到N-1，就可以得到所有的子集。
  需要注意的是，在递归的过程中，会产生重复的子集，需要删除这些子集。
  

  public static void getAllSubSet(int n)
  {
      int[] arrValue = Matrix.initArray(n, 50);
      StringBuffer sb = new StringBuffer();
      for(int value : arrValue) sb.append(value).append("->");
      System.out.println(sb.substring(0, sb.length() - 2));
      
      ArrayList<Integer> list = new ArrayList<Integer>();
      ArrayList<ArrayList<Integer>> subsets = new ArrayList<ArrayList<Integer>>();
      for(int i = 1; i < n; i++)
      {
          subset(arrValue, i, i, list, subsets);
      }
  }
  
  private static void subset(int[] arrValue, int subSetLength, int left, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> subsets)
  {
      if (left == 0 || list.size() == subSetLength)
      {
          boolean bExist = false;
          for(ArrayList<Integer> temp : subsets)
          {
              if (temp.size() == list.size())
              {
                  int j = 0;
                  for (int value : list)
                  {
                      if (!temp.contains(value))break;
                      j++;
                  }
                  if (j == subSetLength) 
                  {
                      bExist = true;
                      break;
                  }
              }
          }
          if (!bExist)
          {
              StringBuffer sb = new StringBuffer();
              for(int value1 : list) sb.append(value1).append("->");
              System.out.println(sb.substring(0, sb.length() - 2));
              subsets.add(list);
          }
          
      }
      for (int temp : arrValue)
      {
          if (list.contains(temp)) continue;
          ArrayList<Integer> listTemp = (ArrayList<Integer>)list.clone();
          listTemp.add(temp);
          subset(arrValue, subSetLength, left - 1, listTemp, subsets);
      }
  }

  执行结果（假设一个长度为4的集合）

  35->6->40->33
  
  35
  6
  40
  33
  35->6
  35->40
  35->33
  6->40
  6->33
  40->33
  35->6->40
  35->6->33
  35->40->33
  6->40->33

• 求给定字符串的所有可能组合（假设字符串没有重复字符）
  思路：这个题目和上面的题目非常类似，只不过这个题目求的是对于长度为N的集合，我们要列出长度为N的“子集”。注意要去除重复组合。
  

  public static void perm(String value)
  {
      char[] arrChars = value.toCharArray();
      char[] arrAlready = new char[arrChars.length];
      ArrayList<char[]> all = new ArrayList<char[]>();
      permRecursive(arrChars, arrChars.length, arrAlready, all);
  }
  
  private static void permRecursive(char[] arrChars, int left, char[] arrAlready, ArrayList<char[]> all)
  {
      if (left == 0)
      {
          boolean bExist = false;
          for(char[] arrTemp : all)
          {
              int j=0;
              for (int i = 0; i < arrChars.length; i++)
              {
                  if (arrTemp[i] != arrAlready[i]) break;
                  j++;
              }
              if (arrChars.length == j)
              {
                  bExist = true;
                  break;
              }
          }
          if (!bExist)
          {
              all.add(arrAlready);
              for(char ch:arrAlready)System.out.print(ch);
              System.out.println();
          }
      }
      for(char ch : arrChars)
      {
          int i = 0;
          for(i = 0; i < arrChars.length - left; i++)
          {
              if (ch == arrAlready[i]) break;
          }
          if (i == arrChars.length - left) 
          {
              arrAlready[arrChars.length - left] = ch;
              char[] arrTemp = arrAlready.clone();
              permRecursive(arrChars, left - 1, arrTemp, all);
          }
      }
  }

  执行结果（以“abc”为例）

  abc
  acb
  bac
  bca
  cab
  cba

• 给出N个'('和')'，列出所有可能的合法组合
  思路：依然使用递归的套路，需要注意已输出的'('的数目不能小于')'的数目。
  

  public static void printPar(int n)
  {
      char[] arrResult = new char[2*n];
      printParRecursive(n, n, arrResult, 0);
  }
  
  private static void printParRecursive(int lCount, int rCount, char[] arrResult, int totalCount)
  {
      if (lCount == 0 && rCount == 0)
      {
          System.out.println(arrResult);
      }
      if (lCount > 0)
      {
          arrResult[totalCount] = '(';
          printParRecursive(lCount - 1, rCount, arrResult, totalCount + 1);
      }
      if (rCount > lCount)
      {
          arrResult[totalCount] = ')';
          printParRecursive(lCount, rCount - 1, arrResult, totalCount + 1);
      }
  }

  执行结果（假设N=4）

  (((())))
  ((()()))
  ((())())
  ((()))()
  (()(()))
  (()()())
  (()())()
  (())(())
  (())()()
  ()((()))
  ()(()())
  ()(())()
  ()()(())
  ()()()()

• 硬币组合，假设我们有25美分、15美分、5美分以及1美分的硬币，硬币的数目不限，对于指定的N美分，请列出所有可能的组合。
  思路：典型的递归，假设已经有25美分，那么需要找出N-25的所有组合，同样需要找出N-15、N-5、N-1的组合。
  

  public static void combine(int n)
  {
      ArrayList<Integer> list = new ArrayList<Integer>();
      ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();
      combinRecursive(n, list, all);
  }
  
  private static void combinRecursive(int n, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> all)
  {
      if (n == 0)
      {
          Collections.sort(list);
          boolean bExist = false;
          for(ArrayList<Integer> temp : all)
          {
              if (temp.size() == list.size())
              {
                  int j = 0;
                  for(int i = 0; i < temp.size(); i++)
                  {
                      if (temp.get(i) != list.get(i)) break;
                      j++;
                  }
                  if (j == temp.size())
                  {
                      bExist = true;
                      break;
                  }
              }
          }
          if (!bExist)
          {
              all.add(list);
              StringBuffer sb = new StringBuffer();
              for(int value1 : list) sb.append(value1).append("->");
              System.out.println(sb.substring(0, sb.length() - 2));
          }
      }
      
      if (n >= 25)
      {
          ArrayList<Integer> temp = (ArrayList<Integer>)list.clone();
          temp.add(25);
          combinRecursive(n - 25, temp, all);
      }
      if (n >= 10)
      {
          ArrayList<Integer> temp = (ArrayList<Integer>)list.clone();
          temp.add(10);
          combinRecursive(n - 10, temp, all);
      }
      if (n >= 5)
      {
          ArrayList<Integer> temp = (ArrayList<Integer>)list.clone();
          temp.add(5);
          combinRecursive(n - 5, temp, all);
      }
      if (n >= 1)
      {
          ArrayList<Integer> temp = (ArrayList<Integer>)list.clone();
          temp.add(1);
          combinRecursive(n - 1, temp, all);
      }
  }

  执行结果（假设N=25）

  25
  5->10->10
  1->1->1->1->1->10->10
  5->5->5->10
  1->1->1->1->1->5->5->10
  1->1->1->1->1->1->1->1->1->1->5->10
  1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->10
  5->5->5->5->5
  1->1->1->1->1->5->5->5->5
  1->1->1->1->1->1->1->1->1->1->5->5->5
  1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->5->5
  1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->5
  1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1->1

  
  
  
  最后，欢迎大家提出更多和递归相关的面试题目，我们可以一起讨论。