Directory Introduction

• 01. What is recursion
• 02. Recursive Three Conditions
• 03. Fibonacci series
• 04. Find all files in the specified directory
• 05.Find 1+2+...+N and
• 06. Find a factorial of 100
• 07. Combination of Ordered Numbers
• 08. Find a multiplier
• 09. Backpack problem
• 10. Select a team
• 11. Hannotta Problem
• 12. Dichotomy Search
• 13. Watch out for duplicate calculations
• 14. Recommendation for Open Source Projects

01. What is recursion

• Recursion: Call yourself within a method.Recursion can be used to solve complex problems with simple programs.For example, the calculation of Pepponacci series, the Hanoi Tower, the fast row and so on.
• The recursive structure consists of two parts:
  • 1. Define recursive headers.Answer: When not to call your own method.If there is no head, it will fall into an infinite loop, which is the end condition of recursion.
  • 2. Recursive body.Answer: When do I need to call my own method?

02. Recursive Three Conditions

• There are three conditions for recursion.This is a very typical example of recursion, so what kind of problems can be solved recursively?I summarize three conditions that can be solved recursively as long as the following three conditions are met at the same time.
• 1. The solution of a problem can be broken down into several subproblems
  • What are the sub-questions?The sub-problem is the smaller size of the data.For example, in the movie theater example mentioned earlier, you need to know that the question of "in which row do you belong" can be broken down into a sub-question of "in which row do you belong to the people in the front row?"
• 2. This problem is the same as the sub-problem after decomposition except for the different data sizes.
  • For example, in the case of the cinema, the way you think about "where are you in the row" is the same as the way people in the previous row think about "where are you in the row".
• 3. There is a recursive termination condition + the problem is decomposed into sub-problems, the sub-problems are decomposed into sub-problems, and decomposed into sub-problems one by one. There can not be an infinite loop, which requires termination conditions.
• Or in the case of a movie theater, people in the first row don't have to ask anyone anymore to know which row they are in, that is, f(1)=1, which is the end of recursion.

03. Fibonacci series

• Title Requirements
  • Everyone knows that the Fibonacci number column. Now you need to enter an integer n. Please output the nth term of the Fibonacci number column.N<=39
• What is a Fibonacci sequence?
  • 1, 1, 2, 3, 5, 8, 13, 21...The Fibonacci sequence starts with the third term, each of which equals the sum of the first two.The Fibonacci Sequence was proposed by mathematician Leonardoda Fibonacci, taking rabbit reproduction as an example, so it is also called the Rabbit Sequence.
• Solving problems
  • It is certain that this problem can be solved recursively, but there is a big problem with it: a large number of recursive, repetitive calculations can cause memory overflow.In addition, the results of the calculation can be saved and multiplexed using fn1 and fn2 using an iterative method.Below I'll give both method sample codes and compare the runtime of the two methods.
• Using an iterative method:

  int Fibonacci(int number) {
  	if (number <= 0) {
  		return 0;
  	}
  	if (number == 1 || number == 2) {
  		return 1;
  	}
  	int first = 1, second = 1, third = 0;
  	for (int i = 3; i <= number; i++) {
  		third = first + second;
  		first = second;
  		second = third;
  	}
  	return third;
  }
  

• Use recursion: f(n) = f(n-1) + f(n-2)

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

• Execution time comparison
  • Assuming n is 40, we use iterative and recursive methods to compute the results as follows:
    • 1. Iteration: Time consuming 1ms
    • 2. Recursion: 272ms
• Why is recursion inefficient
  • If you briefly analyze the execution flow of a program, you will find out what the problem is, for example, calculating Fibonacci(5)
  • From the figure above, it can be seen that in the process of calculating Fib(5), Fib(1) calculated twice, Fib(2) calculated three times, and Fib(3) calculated two times. The tasks that would otherwise only need five calculations were calculated nine times.This problem becomes so prominent as it grows in size that Fib(1000) can no longer be calculated in an acceptable time frame.
  • The simple definition of fib(n) was used, that is, the formula fib(n) = fib(n-1) + fib(n-2).It's easy to think of this idea, but after careful analysis we find that when you call fib(n-1), you also call fib(n-2), which means that fib(n-2) is called twice. Similarly, when you call f(n-2), f(n-3) is called twice, and these redundant calls are completely unnecessary.The complexity that can be calculated for this algorithm is exponential.
• Recursive Iteration Efficiency Comparison
  • Recursive calls are actually functions calling themselves, which is expensive to call. The system allocates storage for each function call and records the call point stack.At the end of the function call, space is also freed and the stack restores the breakpoint.So function calls are not only a waste of space, they are also a waste of time.It wastes a lot of time processing function calls.

04. Find all files in the specified directory

• The questions are as follows:
  • List (or delete) all files in the specified directory
• Instance code, as shown below

  /**
   * Find all files in the specified directory
   * recursion
   *
   * @param files
   * @return
   */
  public static List<File> listFiles(File files) {
      List<File> fileList = new ArrayList<>();
      if (files.isDirectory()) {
          for (File file : files.listFiles()) {
              fileList.addAll(listFiles(file));
          }
      } else {
          fileList.add(files);
      }
      return fileList;
  }
  

• Test Code

  public static void main(String args[]) {
      List<File> l = listFiles(new File("E:\\yc\\JavaProjectTest\\src"));
      System.out.println("common" + l.size() + "Files");
      for (File f : l) {
          System.out.println(f.getName());
          //(Only the filename of the file is printed here)
      }
  }
  

05.Find 1+2+...+N and

• Title Requirements
  • The questions are as follows:
    • Calculate from 1+2+3+...+N and
  • Example:

    Calculate from 1+2+3+...+100 and 5050
    

• Instance code, as shown below

  /**
   * Get the sum from 1+to N
   *
   * @param num
   * @return
   */
  public static int getSum(int num) {
      if (num == 1) {
          return 1;
      }
      return num + getSum(num - 1);
  }
  

• Test Code

  public static void main(String args[]) {
       System.out.println(getSum(100));
  }
  
  //results of enforcement
  5050
  

06. Find a factorial of 100

• The questions are as follows:
  • Find the factorial of 100
• Instance code, as shown below

  	public BigInteger sum(int i) {
  		if (i == 1) {
  			return BigInteger.ONE;
  		}
  		return BigInteger.valueOf(i).multiply(sum(i - 1));
  	}
  

• Test Code

  public static void main(String[] args) {
  	LoopMutiply test = new LoopMutiply();
  	try {
  		System.out.println("yc Calculation results:" + test.sum(50) + "!");
  	} catch (Exception e) {
  		e.printStackTrace();
  	}
  }
  

07. Combination of Ordered Numbers

• The questions are as follows:
  • Give you two ordered arrays, A is {1, 3, 4}, b is {2, 3, 5, 6}. Please synthesize it into a new array and output...
• Instance code, as shown below

  	// Merge Array
  	public static int[] mergeArray(int[] a, int[] b) {
  		int result[] = new int[a.length + b.length];
  		if (checkSort(a) && checkSort(b)) {
  			// Explains that ab arrays are ordered arrays
  			// Define two cursors
  			int i = 0, j = 0, k = 0;
  			while (i < a.length && j < b.length) {
  				if (a[i] <= b[j]) {
  					result[k++] = a[i++];
  				} else {
  					result[k++] = b[j++];
  				}
  			}
  			while (i < a.length) {
  				// Explain that there is still a remaining array of a
  				result[k++] = a[i++];
  			}
  			while (j < b.length) {
  				result[k++] = b[j++];
  			}
  		}
  		return result;
  	}
  	// Check if an array is ordered 1 2 3
  	public static boolean checkSort(int[] a) {
  		boolean flag = false;// Default is not ordered
  		for (int i = 0; i < a.length - 1; i++) {
  			if (a[i] > a[i + 1]) {
  				// Description is not ordered
  				flag = false;
  				break;
  			} else {
  				flag = true;
  			}
  		}
  		return flag;
  	}
  

• test result

  public static void main(String[] args) {
  	int[] a = { 1, 3, 4 };
  	int[] b = { 2, 3, 5, 6 };
  	int[] c = mergeArray(a, b);
  	for (int n : c) {
  		System.out.print(n + " ");
  	}
  }
  

08. Find a multiplier

• The questions are as follows:
  • To find the power of a number
• Example:

  For example, 2^8, we can find the value of expression 2*2*2*2*2*2*2*2*2*2*2, but if the value of y is very large, this may seem like a long expression.So there is no quicker way?
  

• problem analysis
  • Generally, a slightly more complex calculator can find a multiplication of a number. Usually, the symbol on the calculator is a key like x^y, which indicates the Y power of X.How do we usually multiply a number?
  • The mathematical formula is as follows: (Xa)b = Xa*b
  • If we find the power 28, we can first assume 22=a, so 28 = 22) 4, then a4; if a2 = b, a4 = b2, and B2 can be written as (b2)1.So now 28 is converted to: b*b
  • That is, we convert the operation of a multiplier into a multiplication operation.When y is even, it can be converted to multiply two numbers. When y is odd, we have to multiply by an extra x after the return value.
  • X^y=(x^2)^(y/2), define a=x^2,b=y/2, and get the form x^y= a^b;
• Instance code, as shown below

  public static int pow(int x,int y){
      if(x == 0 || x == 1){
          return x;
      }
      if(y > 1){
          int b = y/2;
          int a = x*x;
          if(y%2 == 1){//y is odd
              return pow(a,b)*x;
          }else{//y is even
              return pow(a,b);
          }
      }else if(y == 0){
          return 1;
      }else{//y==1
          return x;
      }
  }
  

• test result

  public static void main(String[] args) {
  	System.out.println("yc Calculation results:" + pow(2,8) + "!");
  }
  

09. Backpack problem

• The questions are as follows:
  • Backpack problems are also a classic problem in computers.In its simplest form, it includes trying to put items of different weights into the backpack so that the backpack finally reaches the specified total weight.
• Example:
  • For example: suppose you want your backpack to weigh exactly 20 pounds, and you have five data items that you can put in. They weigh 11 pounds, 8 pounds, 7 pounds, 6 pounds, and 5 pounds, respectively.The problem may be simple for humans, and we can probably calculate 8 pounds + 7 pounds + 5 pounds = 20 pounds.But if you let the computer solve this problem, you need to set detailed instructions for the computer.
• problem analysis
  • 1. If at any point in the process the sum of selected data items meets the target weight, the work is complete.
  • 2. From the first item selected, the sum of the remaining items must match the target weight of the backpack minus the weight of the first item. This is a new target weight.
  • 3. Try the possibilities of each combination of remaining data items one by one, but be careful not to try all combinations, because you will stop adding data as long as the items are larger than the target weight.
  • 4. If there is no suitable combination, discard the first item and repeat the whole process from the second item.
  • 5. Continue with the third data item, and so on until you have tried all the combinations before you know if there is a solution.
• Instance code, as shown below

  public class Knapsack {
      private int[] weights; //Weight to choose from
      private boolean[] selects; //Is the record selected
  
      public Knapsack(int[] weights){
          this.weights = weights;
          selects = new boolean[weights.length];
      }
  
      /**
       * Find combinations that match weight-bearing
       * @param total Total weight
       * @param index Optional Weight Subscript
       */
      public void knapsack(int total,int index){
          if(total < 0 || total > 0 && index >= weights.length){
              return;//No solution found, go back directly
          }
          if(total == 0){//Total weight is 0, then a solution is found
              for(int i = 0 ; i < index ; i++){
                  if(selects[i] == true){
                      System.out.println(weights[i]+" ");
                  }
              }
              System.out.println();
              return;
          }
          selects[index] = true;
          knapsack(total-weights[index], index+1);
          selects[index] = false;
          knapsack(total, index+1);
      }
  }
  

• test result

  public static void main(String[] args) {
      int array[] = {11,9,7,6,5};
      int total = 20;
      Knapsack k = new Knapsack(array);
      k.knapsack(total, 0);
  }
  

10. Select a team

• The questions are as follows:
  • In mathematics, combinations are a choice of things, regardless of their order.
• Example:
  • For example, there are five mountaineers named A,B,C,D and E.If you want to select three of the five players to climb the mountain, how do you list all the team combinations at this time?(regardless of order)
• problem analysis
  • Or solve it recursively: first, the combination of the five people selects three people into two parts, the first part contains team A, the second part does not contain team A.Assume that the group of three people selected from five is abbreviated as (5,3), specifying that n is the size of the group and k is the size of the group.Then, according to the law, there are:
  • (n,k) = (n-1,k-1) + (n-1,k)
  • For three out of five people,
  • There are: (5,3) = (4,2) + (4,3)
  • (4,2) Indicates that there is already a member of team A, and then selects two of the remaining four players, (4,3) Indicates that team A is removed from five and three of the remaining four players. This adds up to three of the five players.
  • Now you've converted one big problem into two small ones.Choose two from four people (two at a time and three at a time) instead of three from five.
  • It is easy to think of recursive ideas when you select two of the four people and express them as: (4,2) = (3,1) + (3,2).
• Instance code, as shown below

  public class Combination {
      private char[] persons;//All the people in the group to choose from
      private boolean[] selects;//Mark whether member is selected, check true
  
      public Combination(char[] persons){
          this.persons = persons;
          selects = new boolean[persons.length];
      }
      public void showTeams(int teamNumber){
          combination(teamNumber,0);
      }
      /**
       *
       * @param teamNumber Number of team members to select
       * @param index Choose from the number of players
       */
      public void combination(int teamNumber,int index){
          if(teamNumber == 0){//When teamNumber=0, find a group
              for(int i = 0 ; i < selects.length ; i++){
                  if(selects[i] == true){
                      System.out.print(persons[i]+" ");
                  }
              }
              System.out.println();
              return;
          }
          //index exceeds the total number of people in the group, indicating that it was not found
          if(index >= persons.length ){
              return;
          }
          selects[index] = true;
          combination(teamNumber-1, index+1);
          selects[index] = false;
          combination(teamNumber, index+1);
      }
  }
  

• test result

  public static void main(String[] args) {
      char[] persons = {'A','B','C','D','E'};
      Combination cb = new Combination(persons);
      cb.showTeams(3);
  }
  

11. Hannotta Problem

• The questions are as follows:
  • The Hanoi Tower Problem is an old puzzle composed of many plates placed on three towers.All plates have different diameters, and there is a hole in the center of the plate that makes them fit exactly on the tower base.All the plates were initially placed on Tower A.The goal of this puzzle is to move all the plates from Tower A to Tower C, one plate at a time, and none of them can be placed on a smaller plate than yourself.
• Example:
  • Just imagine if there are only two plates, and we name them as numbers (or diameters, as you can imagine). Two plates are Plate 1 above and Plate 2 below. Then we just need to move Plate 1 onto Tower B first, then Plate 2 onto Tower C, and finally Plate 1 onto Tower C.That is to complete the movement of two plates from A to C.
  • If there are three plates, we will put tray 1 on Tower C, tray 2 on Tower B, tray 1 on Tower C on Tower B, tray 3 on Tower A on Tower C, tray 1 on Tower B on Tower A, tray 2 on Tower B on Tower C, and finally tray 1 on Tower A on Tower C.
• problem analysis
  • If there are four, five and N plates, what should we do?Recursive thinking solves this problem very well at this point. When there are only two plates, we only need to use Tower B as the intermediary, first place Plate 1 on Tower B, then Place Plate 2 on Target Tower C, and finally Place the plate on Mediation Tower B on Target Tower C.
  • So no matter how many plates we have, we think of them as just two.Assuming that there are N plates on Tower A, we consider them to be two plates, of which (N-1)~1 plate is considered to be one plate and the bottom N plate is considered to be one plate, then the solution is:
    • 1. First treat the plate number (N-1)~1 of Tower A as a plate, place it on the intermediate tower B, and then place the plate number N on the target tower C.
    • (2) Tower A is then empty and is considered to be an intermediate tower. Tower B has N-1 plates at this time. View (N-2)~1 plates as a plate, place them on Tower A, and then place tray No. (N-1) of Tower B on Target Tower C.
    • (3) There are (N-2) plates on Tower A, Tower B is empty, and Tower B is treated as intermediate tower. Repeat steps 1 and 2 until all the plates are placed on target tower C.
  • Simply put, like putting an elephant in a refrigerator, the recursive algorithm is:
    • 1. Move the plate containing n-1 from the initial tower A to the intermediate tower B.
    • (2) Place one of the remaining plates (the largest) on the initial tower A on the target tower C.
    • (3) Move n-1 plates on Intermediate Tower B to target tower C.
• Instance code, as shown below

  /**
   * Hannotta problem
   * @param dish Number of plates (also known as names)
   * @param from Initial Tower
   * @param temp Medium Tower
   * @param to   Target Tower
   */
  public static void move(int dish,String from,String temp,String to){
      if(dish == 1){
          System.out.println("Put the plate on"+dish+"From Tower"+from+"Move to Target Tower"+to);
      }else{
          move(dish-1,from,to,temp);//A is the initial tower, B is the target tower, C is the Intermediate Tower
          System.out.println("Put the plate on"+dish+"From Tower"+from+"Move to Target Tower"+to);
          move(dish-1,temp,from,to);//B is the initial tower, C is the target tower, A is the Intermediate Tower
      }
  }
  

• test result

  move(3,"A","B","C");
  

12. Dichotomy Search

• The questions are as follows:
  • A series of arrays, then find the index of a value
• problem analysis
  • It must be an ordered table, either ascending or descending
• Instance code, as shown below

  /**
   * @param array Ordered arrays, but not limited to arrays
   * @param start Array subscript to start lookup
   * @param end End Lookup Array Subscript
   * @param searchValue Value to search for
   * @return
   */
  public static int search(int[] array, int start, int end, int searchValue){
      if (array != null && array.length > 0){
          int middle = (start + end) / 2;
          int middleValue = array[middle];
          if (searchValue == middleValue){
              return middle;
          }else if (searchValue < middleValue){
              //Query value is less than median, search again before median, narrow range
              return search(array, start, middle-1, searchValue);
          }else {
              //Query value is larger than median value, search again after median value to narrow down
              return search(array, middle+1, end, searchValue);
          }
      }else {
          return -1;
      }
  }
  

• test result

  public static void main(String[] args) {
      int[] array = {1,3,5,7,9,12,14,15,19,20,22,23,28,30};
      System.out.println(search(array, 0, array.length-1, 20));
  }
  

13. Watch out for duplicate calculations

• In addition, there are problems with duplicate calculations when using recursion.The third example of recursive code just mentioned, if we break down the entire recursive process, is this:
• To calculate f(5), f(4) and f(3) need to be calculated first, and f(4) needs to be calculated f(3), so f(3) has been calculated many times, which is a duplicate calculation problem.
• To avoid duplicate calculations, we can save the solved f(k) through a data structure such as a hash list.When f(k) is called recursively, see if it has been solved.If so, the values are returned directly from the hash list, and there is no need to recalculate them, so you can avoid the problem you just talked about.
• Following the ideas above, let's transform the code just now:

  public int Fibonacci(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
  
    // hasSolvedList can be understood as a Map, where key is n and value is f(n)
    if (hasSolvedList.containsKey(n)) {
      return hasSovledList.get(n);
    }
  
    int ret = f(n-1) + f(n-2);
    hasSovledList.put(n, ret);
    return ret;
  }
  

• In addition to the two common problems of stack overflow and repeated calculation.There are many other issues with recursive code.In terms of time efficiency, there are many more function calls in the recursive code, which can accumulate into a considerable time cost when the number of these function calls is large.

14. Recommendation for Open Source Projects

• 1. Summary of open source blogs
• 2. Componentized Practice Projects (stop maintenance)
• 3. Video Player Encapsulation Library
• 4. State Switch Manager Encapsulation Library
• 5. Complex RecyclerView Encapsulation Library
• 6. Pop-up Encapsulation Library
• Version Update Encapsulation Library
• 8. Status Bar Encapsulation Library
• 9. Lightweight Thread Pool Encapsulation Library
• 10. Carousel Map Encapsulation Library
• 11. Audio Player
• 12. Gallery and picture zoom controls
• 13.Python multi-channel packaging
• 14. Overall Side Slider Encapsulation Library
• 15.Python Crawler Sister Map
• 17. Customize the progress bar
• 18. Customize Fold and Expand Layout
• 19. Page loading of commodity details page
• 20. Set a red dot control on any View control
• 21. Dummy slides one page at a time to play the video library
• 22. Tencent x5 Open Source Library