1, Overview of method recursion
1. What is method recursion
The form in which a method calls itself directly or indirectly is called method recursion.
As an algorithm, recursion is widely used in programming languages.
2. Recursive form
Direct recursion: the method calls itself.
Indirect recursion: the method calls other methods, and other methods call back the method itself.
3. Problems with recursion
If the termination of recursion is not well controlled, a recursive dead loop will occur, resulting in stack memory overflow.
Code demonstration: (adjust yourself)
public static void main(String[] args) {
test();
}
private static void test() {
System.out.println("===============test Executed=================");
test1();//Method recursion, direct recursive form (dead loop, resulting in crash)
}
private static void test1() {
System.out.println("===============test1 Executed=================");
test2();//Method recursion, direct recursive form (dead loop, resulting in crash)
}
private static void test2() {
System.out.println("===============test2 Executed=================");
test();//Method recursion, direct recursive form (dead loop, resulting in crash)
//===============test1 is executed=================
//===============test2 is executed=================
//===============test is executed=================
}
II. Recursive algorithm flow and core elements
1. Case: calculate the factorial of 1-n
Requirements: calculate the factorial result of 1-n and solve it with recursion. First, we understand the process and core points of recursion from mathematical thinking.
Analysis: if we think that there is a formula f(n) = 1*2*3*4*5*6*7 *... (n-1)*n;
Then the equivalent form of the formula is: f(n) = f(n-1) *n
If we find the factorial result of 1-5, how should we apply the above formula manually.
The idea of recursive problem solving: turn a complex problem layer by layer into a smaller problem similar to the original problem.
The three elements of recursive algorithm can be summarized as follows:
Recursive formula: f(n) = f(n-1) * n;
Endpoint of recursion: f(1)
The direction of recursion must go to the endpoint;
public static void main(String[] args) {
System.out.println(f(5));//120
}
private static int f(int n) {
if(n == 1){
return n;
}else{
return f(n - 1)*n;
}
}2. Case: calculate the sum of 1-n
Requirements:
The result of calculating the sum of 1-n is solved by using the idea of recursion. First, we understand the process and core point of recursion from the perspective of mathematical thinking.
analysis:
Suppose we think that there is a formula f(n) = 1 + 2 + 3 + 4 + 5 + 6 + 7 +... (n-1) + n;
Then the equivalent form of the formula is: f(n) = f(n-1) + n
Endpoint of recursion: f(1) = 1
If the result is the sum of 1-5, how should it be calculated.
public static void main(String[] args) {
System.out.println(f(10));//55
}
private static int f(int n) {
if(n == 1){
return 1;
}else{
return f(n-1) + n;
}
}3. Classic case: monkey eating peach
Title:
On the first day, the monkey picked several peaches and ate half of them immediately. He felt very good, so he ate one more. The next day, he ate half of the remaining peaches of the previous day. He felt very good, so he ate one more. After that, he ate half of the remaining peaches of the previous day every day, I ate another one and found that there was only one peach on the 10th day.
Requirements:
How many peaches did the monkey pick on the first day?
analysis:
On the whole, every day is the same event, a typical regularization problem,
Consider three elements:
Recursive formula:
Return endpoint:
Recursive direction:
public static void main(String[] args) {
System.out.println(f(1));//1534
System.out.println(f(2));//766
System.out.println(f(3));//382
}
private static int f(int n) {
if(n == 10){
return 1;
}
else{
return 2*f(n + 1) + 2;
}
}3, Transformation of irregular cases
1. Cases: File Search
Requirements:
File search: search a file name from the C: disk and output the absolute path.
analysis:
First locate the first level file object
Traverse all first level file objects,
Judge whether it is a file. If it is a file, judge whether it is what you want
If it is a folder, you need to continue recursion and repeat the above process
public static void main(String[] args) {
//2. Incoming directory and file name
searchFile(new File("D:/"),"t0e2622116992e6377c47f6e7d4a18d82.kgtemp");
}
/**
* 1,Search all the files in a directory and find the files we want
* @param dir Source files searched
* @param fileName Name of the file being searched
*/
public static void searchFile(File dir, String fileName){
//3. Determine whether dir is a directory
if(dir != null && dir.isDirectory()){
//You can find it
//4. Extract the first level file object in the current directory
File[] files = dir.listFiles(); //null []
//5. Judge whether there is a level-1 file object, which can be traversed only if it exists
if(files != null && files.length > 0){
for (File file : files) {
//6. Judge whether the first level file object currently traversed is a file or a folder (directory)
if(file.isFile()){
//7. Is it what we're looking for? Just output its path
if(file.getName().contains(fileName)){
System.out.println("eureka" + file.getAbsolutePath());
//Start it!
Runtime r = Runtime.getRuntime();
try {
r.exec(file.getAbsolutePath());
} catch (IOException e) {
e.printStackTrace();
}
}else{
//8. If it is a folder, you need to continue to search recursively
searchFile(file,fileName);
}
}
}
}
}else{
System.out.println("Sorry, the current search location is not a folder");
}
}
2. Case: Beer problem
Demand: beer costs 2 yuan per bottle, one bottle can be replaced with four caps, and one bottle can be replaced with two empty bottles,
How many bottles of wine can I drink for 10 yuan, and how many empty bottles and lids are left.
Answer: 15 bottles 3 caps 1 bottle
//Define a static member variable to store the quantity you can buy
public static int totalNumber;//Total quantity
public static int lastcoverNumber;//Record the number of bottles remaining each time
public static int lastBottleNumber;// Record the number of caps remaining each time
public static void main(String[] args) {
//1. Buy wine with money
buy(10);
System.out.println("total: " + totalNumber);
System.out.println("Number of remaining covers: " + lastcoverNumber);
System.out.println("Number of bottles remaining: " + lastBottleNumber);
}
private static void buy(int money) {
//2. See how much wine you can buy right away
int buyNumber = money /2; // 5
totalNumber += buyNumber;
//3. Convert the bottle cap and lid into money
//Count the total number of bottle caps and bottles in this round
int coverNumber = lastcoverNumber + buyNumber;
int BottleNumber = lastBottleNumber + buyNumber;
//Statistics of money that can be converted
int allMoney = 0;
if(coverNumber >= 4){
allMoney += (coverNumber / 4 ) * 2;
}lastcoverNumber = coverNumber % 4 ;
if(BottleNumber >=2){
allMoney += (BottleNumber / 2) * 2;
}lastBottleNumber = (BottleNumber % 2);
if(allMoney >=2){
buy(allMoney);
}
}