Recursive cases of algorithms
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 subquestions?The subproblem 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 subquestion of "in which row do you belong to the people in the front row?"
 2. This problem is the same as the subproblem 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 subproblems, the subproblems are decomposed into subproblems, and decomposed into subproblems 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(n1) + f(n2)
public int Fibonacci(int n) {
if (n <= 0) {
return 0;
}
if (n == 1n==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(n1) + fib(n2).It's easy to think of this idea, but after careful analysis we find that when you call fib(n1), you also call fib(n2), which means that fib(n2) is called twice. Similarly, when you call f(n2), f(n3) 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 weightbearing
* @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(totalweights[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) = (n1,k1) + (n1,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(teamNumber1, 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 (N1)~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 (N1)~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 N1 plates at this time. View (N2)~1 plates as a plate, place them on Tower A, and then place tray No. (N1) of Tower B on Target Tower C.
 (3) There are (N2) 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 n1 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 n1 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(dish1,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(dish1,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, middle1, 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.length1, 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(n1) + f(n2);
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.
Keywords:
Mobile
calculator
Python
less
Added by Corvin on Fri, 20 Dec 2019 03:56:33 +0200