Recursive cases of algorithms

catalogue

01. What is recursion
02. Recursion three conditions
03. Fibonacci numbers
04. Find all files in the specified directory
05. O 1 + 2 +… + N and
Find the factorial of 100
07. Ordered array merge
Find a number to power
09. Backpack problem
Pick a team
11. The Hannotta problem
12. Binary search
13. Be wary of double counting
14. Open source project recommendations

01. What is recursion

Recursion: A call to itself within a method. Using recursion can use simple procedures to solve some complex problems. For example: pei Bonacci sequence calculation, Hannott tower, fast row and other problems.
The recursive structure consists of two parts:
- Define the recursion header. Answer: when not to call its own method. If you don’t have a head, you’re stuck in an infinite loop, which is the end condition of the recursion.
- 2. Recursive body. Answer: When you need to call your own method.

02. Recursion three conditions

Recursion needs to satisfy three conditions. This example is very typical of recursion, so what kind of problem can be solved by recursion? I’ve summarized three conditions, and as long as the following three conditions are met, it can be solved recursively.
1. The solution of a problem can be decomposed into several subproblems
- What are the subproblems? The subproblem is the problem of smaller data size. For example, in the movie theater example, you need to know that the problem of “what row you are in” can be decomposed into a sub-problem of “what row are the people in front of you in?”
2. This problem is exactly the same as the decomposed sub-problem except for the different data scale
- For example, in the movie theater, the way you solve “what row are you in” is exactly the same way that the people in front of you solve “what row are you in?”
3. There is a recursive termination condition + decompose the problem into sub-problems, and then decompose the sub-problems into sub-problems, and then decompose the sub-problems layer by layer. There cannot be an infinite cycle, which requires termination conditions.
Again, in the movie theater, the people in the first row know what row they are in without asking anyone else, which is f(1)=1, and that’s the termination condition for recursion.

03. Fibonacci numbers

Topic request
- Everybody knows the Fibonacci sequence, and now I want an integer n, so I want you to print the NTH term of the Fibonacci sequence. n<=39
What are Fibonacci numbers?
- 1,1,2,3,5,8,13,21…… The Fibonacci sequence starts with the third term, and each term is equal to the sum of the first two. The Fibonacci sequence was developed by mathematician Leonardoda Fibonacci using rabbit breeding as an example, so it is also called the “rabbit sequence”.
Their thinking
- You can be sure that this problem can be solved recursively, but there is a big problem with this problem, which is that recursively a lot of repetitions can cause memory overflow. In addition, the iterative method can be used to save the results of the calculation in fN1 and Fn2 and reuse them. I’ll show you the sample code for both methods and give a comparison of their running times.

Using 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;
}
Copy the code

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);
}
Copy the code

Execution time comparison
- Assuming that n is 40, we use the iterative method and recursive method respectively to calculate, and the calculation results are as follows:
  - 1. Iterative method: it takes 1ms
  - 2. Recursion: 272ms
Why is recursion inefficient
- If you look at the execution flow of the program, you can see where the problem is. Take Fibonacci(5) for example
- As can be seen from the figure above, in the process of calculating Fib(5), Fib(1) is computed twice, Fib(2) three times, and Fib(3) twice, and the task that could have been done only five times is computed nine times. This problem becomes more pronounced as the size increases, to the point where Fib(1000) can no longer be calculated in an acceptable time.
- So what we did was we simply defined fib of n, which is we used the formula fib of n is equal to fib of n minus 1 plus fib of n minus 2. It’s easy to think of that, but if you look at it carefully, when you call fib of n-1, you also call FIB of n-2, which means you call FIB of n-2 twice, and you call F of n-2, which means you call F of n-3 twice, you don’t have to make these redundant calls. You can calculate that the complexity of this algorithm is exponential.
Recursive iteration efficiency comparison
- Recursive call is actually the function itself in the call itself, and the function call overhead is very large, the system to allocate storage space for each function call, and will call the stack record. At the end of the function call, but also free space, bounce to restore the breakpoint. So function calls are not only a waste of space, they are also a waste of time. Much of its time is wasted processing function calls.

04. Find all files in the specified directory

The problem is as follows:
- Lists (or deletes) all files in the specified directory

The example code is shown below

/** * find all files in the specified directory ** * @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;
}
Copy the code

The test code

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

05. O 1 + 2 +… + N and

Topic request
- The problem is as follows:
  - Calculated from 1 + 2 + 3 +… And of + N
- Example:
```
Calculated from 1 + 2 + 3 +... The sum of plus 100 is 5,050Copy the code
```

The example code is 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);
}
Copy the code

The test code

public static void main(String args[]) { System.out.println(getSum(100)); } // Result 5050Copy the code

Find the factorial of 100

The problem is as follows:
- Take the factorial of 100

The example code is shown below

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

The test code

public static void main(String[] args) {
	LoopMutiply test = new LoopMutiply();
	try {
		System.out.println("Yc calculation result:" + test.sum(50) + "!"); } catch (Exception e) { e.printStackTrace(); }}Copy the code

07. Ordered array merge

The problem is as follows:
- Give you two ordered arrays, A is {1, 3, 4}, b is {2, 3, 5, 6}, please combine them into a new array, and print…

The example code is shown below

Public static int[] mergeArray(int[] a, int[] b) {int result[] = new int[a.length + b.length];if(checkSort(a) &&checksort (b)) {// 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. ength) {/ / suggests a array are remaining result = [k++] a [i++]; }while(j < b.length) { result[k++] = b[j++]; }}returnresult; } public static Boolean checkSort(int[] a) {Boolean flag =false; // The default is not orderedfor (int i = 0; i < a.length - 1; i++) {
		if(a[I] > a[I + 1]) {// Indicates that flag = is not orderedfalse;
			break;
		} else {
			flag = true; }}return flag;
}
Copy the code

The test results

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 + ""); }}Copy the code

Find a number to power

The problem is as follows:
- Find the power of a number

Example:

For example, 2^8, we could evaluate the expression 2*2*2*2*2*2*2*2 *2, but if y is very large, that would make the expression very verbose. Is there a faster way?Copy the code

Problem analysis
- So if you have a calculator that’s a little bit more complicated, you can multiply a number, and usually the calculator is marked with a button like x to the y, which means you raise x to the y. How do we multiply a number in general?
- The mathematical formula is as follows :(Xa)b = Xa*b
- If we were to take the twenty-eighth power, we could assume that twenty-two is equal to a, so twenty-eight is equal to twenty-two four, so a4; If A2 is equal to b, then A4 is equal to b2, and B2 can be written as (b2)1. So now 28 becomes b times b
- In other words, we’re converting the power operation to the multiplication operation. If you take the value of xy, when y is even, you end up multiplying two numbers, and when y is odd, you end up having to multiply the return value by an extra x.
- X ^y= (x^2)^(y/2) = (x^2)^(y/2) = (x^2)^(y/2)

The example code is 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 oddreturn pow(a,b)*x;
        }else{/ / y is an even numberreturnpow(a,b); }}else if(y == 0){
        return 1;
    }else{//y==1
        returnx; }}Copy the code

The test results

public static void main(String[] args) {
	System.out.println("Yc calculation result:"(2, 8) + + pow"!");
}
Copy the code

09. Backpack problem

The problem is as follows:
- The knapsack problem is also a classic problem in computers. In its simplest form, this involves trying to put items of different weights into the backpack so that the backpack ends up with a specified total weight.
Example:
- For example, imagine that the backpack could hold exactly 20 pounds and that there were five data items that could fit in, each weighing 11 pounds, 8 pounds, 7 pounds, 6 pounds, and 5 pounds. The problem might be simple enough for humans to figure out that 8 pounds + 7 pounds + 5 pounds = 20 pounds. But if you let a computer solve this problem, you need to set detailed instructions for the computer.
Problem analysis
- If, at any point in the process, the sum of the selected data items matches the target weight, the job is done.
- 2. Starting from the first item selected, the sum of the remaining items must correspond to the target weight of the backpack minus the weight of the first item, which is a new target weight.
- Third, try each possible combination of remaining data items one by one, but be careful not to try all combinations, because as long as the sum of data items is greater than the target weight, stop adding data.
- If there is no suitable combination, discard the first item and repeat the whole process from the second item.
- Continue with the third data item, and so on until you have tried all the combinations, at which point you will not know if there is a solution.

The example code is shown below

public class Knapsack { private int[] weights; Private Boolean [] selects; Public Knapsack(int[] weights){this.weights = weights; selects = new boolean[weights.length]; } public void knapsack(int total,int index){public void knapsack(int total,int index){if(total < 0 || total > 0 && index >= weights.length){
            return; // If no solution is found, return directly to}if(total == 0){// The total weight is 0, then the solution is foundfor(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); }}Copy the code

The test results

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); }Copy the code

Pick a team

The problem is as follows:
- In mathematics, a combination is a choice of things regardless of their order.
Example:
- For example, there are five mountaineers named A,B,C,D and E. Want to choose three of the five players to climb the mountain, how to list all the team combinations. (Regardless of order)
Problem analysis
- The solution is still to be solved recursively: first of all, the combination of five people is divided into three parts, the first part contains team A, and the second part does not contain team A. Suppose we abbreviate the combination of three out of five people to (5,3), specifying that n is the size of the group and k is the size of the group. So according to the rule we can have:
- (n,k) = (n-1,k-1) + (n-1,k)
- For choosing 3 people out of 5,
- So :(5,3) = (4,2)+(4,3)
- (4,2) means there is already player A, and two players are selected from the remaining four, (4,3) means that player A is removed from the five, and three players are selected from the remaining four, which adds up to three players from the five.
- Now I’ve turned one big problem into two small ones. Make two choices from a group of four (two at a time and three at a time) rather than three from a group of five.
- Choosing two people from a group of four can be expressed as :(4,2) = (3,1) + (3,2), and so on, and it’s easy to think of recursion.

The example code is shown below

public class Combination { private char[] persons; Private Boolean [] SELECTS; // Flag whether the member is selectedtruepublic Combination(char[] persons){ this.persons = persons; selects = new boolean[persons.length]; } public void showTeams(int teamNumber){ combination(teamNumber,0); } /** ** @param teamNumber * @param index */ public void combination(int teamNumber,int index){if(teamNumber == 0){// When teamNumber=0, find a groupfor(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 members in the groupif(index >= persons.length ){
            return;
        }
        selects[index] = true;
        combination(teamNumber-1, index+1);
        selects[index] = false; combination(teamNumber, index+1); }}Copy the code

The test results

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

11. The Hannotta problem

The problem is as follows:
- The Hannott tower problem is an ancient conundrum consisting of a number of plates placed on three towers. All the plates are different in diameter and have a hole in the middle so they fit on the tower. All the dishes were initially placed on tower A. The object of this puzzle is to move all the plates from Tower A to Tower C, one at A time, and no plate should be placed on top of A smaller plate.
Example:
- Imagine if there are only two plates, plates since we named after digital (can also imagine diameter), two dish is above 1, below is the plate 2, so we only need 1 plates to move to the first tower B, then 2 plates move to tower C, finally moved to 1 C tower plates. That’s two plates going from A to C.
- If there are three plates, then we put the tray 1 in tower C, 2 plate into the B tower, the tower plate 1 C on tower B, then A 3 on C tower tower plate, and then put the plate tower 1 B in A tower, put the tray tower 2 B in tower C, finally put A plate tower 1 C on the tower.
Problem analysis
- If we have four, five, N plates, then what do we do? When there are only two plates, we only need to take Tower B as the intermediary, put plate 1 on the intermediary tower B, then put plate 2 on the target tower C, and finally put the plate from tower B on the target tower C.
- So no matter how many plates there are, we’re going to treat it as just two plates. Suppose there are N plates on tower A, which we regard as two plates, where (n-1)~1 plates are regarded as one plate, and the NTH plate at the bottom is regarded as one plate, then the solution is as follows:
  - ① First, regard the (n-1)~1 plate in Tower A as A plate and put it on the intermediary tower B, then put the NTH plate on the target tower C.
  - ② Then tower A is empty and regarded as an intermediary tower. At this time, there are n-1 plates in Tower B. The plates (N-2)~1 are regarded as A plate and placed on the intermediary tower A. Then, the plates (N-1) in tower B are placed on the target tower C.
  - ③ At this time, tower A has (N-2) plates, tower B is empty, and tower B is regarded as an intermediary tower. Repeat steps ① and ② until all the plates are placed on the target tower C.
- In simple terms, the recursive algorithm is the same as putting an elephant in a refrigerator:
  - ① Move n-1 plates from the initial tower A to the intermediate tower B.
  - ② Place the remaining plate (the largest plate) from the initial tower A on the target tower C.
  - ③ Move N-1 plates on the intermediary tower B to the target tower C.

The example code is shown below

/** * @param dish * @param from initial tower * @param temp * @param to target tower */ public static void move(int dish,String from,String temp,String to){if(dish == 1){
        System.out.println("Turn the plate"+dish+"From the 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"Turn the plate"+dish+"From the 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}}Copy the code

The test results
```
move(3,"A"."B"."C");
Copy the code
```

12. Binary search

The problem is as follows:
- A series of arrays and find the index of a value
Problem analysis
- It must be an ordered list, either ascending or descending

The example code is shown below

/** * @param array Ordered array, but not limited to array * @param start array index to start the search * @param end array index to end the search * @param searchValue Value to search * @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){// if the value is smaller than the middleValue, search again before the middleValue to narrow the rangereturn search(array, start, middle-1, searchValue);
        }else{// If the value of the query is greater than the median value, search again after the median value to narrow the rangereturnsearch(array, middle+1, end, searchValue); }}else {
        return -1;
    }
}
Copy the code

The test results

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

13. Be wary of double counting

In addition, there is the problem of double calculation when recursion is used. The third example of recursive code, if we break it down, looks something like this:
If you want to compute f(5), you have to compute f(4) and f(3), and if you want to compute F (4), you have to compute f(3), so f(3) is computed many times, and that’s the double counting problem.
To avoid double-counting, we can use a data structure (such as a hash table) to store the solved f(k). When I recursively call f(k), let’s see if I’ve solved it. If it is, it returns the value directly from the hash table without double-counting, thus avoiding the problem we just described.

Let’s modify the code as follows:

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

In addition to stack overflow, double calculation these two common problems. There are many other problems with recursive code. In terms of time efficiency, there are many more function calls in the recursive code, and when the number of these function calls is large, it can add up to a significant time cost.

14. Open source project recommendations

1. Open source blog aggregation
2. Componentized practice project (stop maintenance)
3. Video player packaging library
4. State switch manager encapsulates the library
5. Complex RecyclerView packaging library
6. Popover encapsulation library
7. Version update package library
8. Status bar encapsulates library
9. Lightweight thread pool encapsulation library
10. Multicast map encapsulation library
11. Audio player
12. Gallery and picture zoom control
13.Python multi-channel packaging
14. Overall sideslip animation package library
15.Python crawler girl graph
17. Customize the progress bar
18. Custom collapse and expand layouts
19. Product details page is loaded in pages
20. Set the red dot control on any View control
21. Play video library by swiping one page at a time
Tencent X5 open source library

catalogue

01. What is recursion

02. Recursion three conditions

03. Fibonacci numbers

04. Find all files in the specified directory

05. O 1 + 2 +… + N and

Find the factorial of 100

07. Ordered array merge

Find a number to power

09. Backpack problem

Pick a team

11. The Hannotta problem

12. Binary search

13. Be wary of double counting

14. Open source project recommendations

Related Posts

Android — Gradle

Flutter draw – 03 – Paint

Elegantly encapsulates the Activity Result API, a perfect replacement for startActivityForResult()