Introduction to recursive idea and implementation, eliminating recursion

On the understanding of recursion

---

Here is my personal understanding , Probably Yes, maybe not , There is reference value to borrow some praise
Recursion is interpreted as ： Is a programming technique that calls itself . It looks simple , Just call yourself , Calling your own function in the function body is a recursive technique , Pay attention to the conditions for the end of recursion, otherwise infinite recursion will lead to memory overflow . If you only understand it this way, it seems that you haven't used recursion except that you can read the ingenious recursion algorithm written by others , I don't know when to use recursion, but when I find others using recursion, I feel “ Wonderful can be written like this ”, According to other people's ideas, you can write recursion and go around. You are dizzy , still copy Someone else's . So the most important thing is to understand the idea , Only by solving problems from a deep level of thinking can they be transformed into their own things .

recursive thinking ： Recursion is actually an idea of divide and rule （ Divide and conquer algorithm ）, First, turn big problems into small ones , Then solve the small problems one by one and merge them into the solution of the original problem , Since it can be solved recursively , Then the model for solving big problems and divided small problems should be the same to call their own functions , It's called a recursive model , Using the idea of recursion, programmers are building such a model to become a recursive model . The recursive procedure is “ Deliver ” and “ return ” Two processes , First, the large problem is transferred to the smaller problem through certain calls （ The process of turning big into small ）, When certain conditions are met, the delivery ends , The process of solving problems one by one in the return stage （ Solve small problems first and then merge to solve big problems ）.（ Recursion without return is not a recursive algorithm , It should belong to dynamic planning . So it must be a recursive and regressive model ）

step ： Now that you know that recursion is a process of enlarging and reducing , The process of "small hit big" , In programming, there is a technical support that allows functions to call themselves , The next step is the user's job , How to make big problems small so that we can hit big problems with small ones ？ This process is the establishment of recursive model . Such a model （ That is, the function written ） What conditions should there be ？ The problem can be divided into smaller problems layer by layer , And it can solve small problems layer by layer and merge them into the solution of the original problem , It can be divided into many types, but it must be able to merge and solve at the same time , Therefore, we should start with the aspects that can merge small problems into big ones , Conclude that you can **“ return ” And a solution to a big problem , The difficulty of this thinking is to ask the programmer to call out the inertia of the original way of thinking , Think another way , So it feels very strange, so it's the difficulty , The past thinking point is , Start from a big problem, solve a small part, and then throw out smaller problems to solve （ Here is an example of quick sort , Quicksort is easy to understand and write , There is no feeling around because it conforms to the way we usually think , It is divided into two parts first, and then smaller parts on the basis of the two parts , When the smaller parts are solved, the sorting is finished , There is no process of return , So it's easy to understand the code, and it's not too confusing ）, The way of thinking about recursive problem solving is First turn big problems into small problems, first solve small problems, then solve bigger problems on the basis of small problems, and then solve big problems layer by layer **（ Like recursive sorting , Sort the small parts first , And then sort the larger part based on the small part , Finally, sort the whole sequence ）. This kind of reverse thinking from a big problem is quite laborious and dizzy every minute , But here's a good math tool ----- Mathematical induction

Draw lessons from 《 Recursion and mathematical induction 》
Mathematical induction , Everyone must have learned mathematical induction , When we need to prove a proof problem , Mathematical induction is likely to be used , The idea of mathematical induction is as follows ：
In a general way , Prove a relation with natural number n The related proposition P(n）, There are the following steps ：
（1） Proof when n Take the first value n0 The proposition of time holds .n0 For general series, the value is 0 or 1, But there are also special cases ;
（2） Suppose that n=k（k≥n0,k For natural Numbers ） The proposition of time holds , Proof when n=k+1 The proposition of time also holds .
comprehensive （1）（2）, For all natural numbers n（≥n0）, proposition P(n） All set up .
Actually , Mathematical induction uses the principle of recursion , Figuratively, it can be called the domino principle . because N+1 Is established, all numbers can be recursively forward and backward .
Recursion also uses the principle of recursion , In the whole process , The same principle will be implemented repeatedly . At this point , Recursion is essentially the same as mathematical induction . Mathematical induction is the reverse implementation of forward thinking recursion , Start from the smallest problem and find a solution instead of thinking directly from the big problem , I feel the relationship between computer and mathematics , Computer is the son of mathematics …… So we can use mathematical induction to design the implementation of recursion .
The steps of designing recursive programs by induction ：
One 、 Analyze problems by mathematical induction , According to the first step of mathematical induction, the ending part .
Two 、 According to the second step of mathematical induction, the recursive part of the constructor . In fact, the solution process is to find R(N) And R(N-1) The relation of .

Solving Hanoi Tower problem by recursion

---

hypothesis n A plate from from With the help of temp Move to, The top is the first
imagine , If there is only one plate, go directly from from Move to to That's all right.
If there are two plates, move the first plate to temp And then move the second plate to then temp Move to to On
Three plates …………

Thinking from another angle , In fact, every time we move, we will first think about how to move the current top to to On , That is to say, the way of thinking is to move the first, then the second, and then the third , Then I found that I had to move this to the bottom of the place to move it out and back again , Then I found that all the way back and forth is to move this. First move the small side, then move the large side, and then put the small one on the large one , Then move the big one …… Found the boring side of repetition , I feel fresh just playing , Playing with it, I found that it was always the same. At most, there were more and more plates, which were pulled back and forth repeatedly …… And computing is good at this boring and repetitive work . The above rules are the same no matter how many plates , That is to say, it gives a recursive but , That is to say, moving the second one is based on moving the first one , Move the first one away and move the second one directly , The third is to move both the second and the first directly ……
Each plate should be moved to the target column , Must rely on the upper plate to move to the column of the auxiliary group first This is the idea of recursion , First turn big problems into small problems, first solve small problems, then solve bigger problems on the basis of small problems, and then solve big problems . Think in another way , Not thinking about going from the first to the second …… Move all the way to the last , But thinking about moving the last one is the biggest one , First move all the above to temp On the pillar of , Then move the largest one to to On , To move the top to temp On the pillar of , You can't move directly, so you can only move one by one , First move the bottom with the help of to Move to temp…… Until there is only one, you can move directly and return , Is the condition of recursion . This kind of thinking is hard to think of , Because it does not belong to conventional thinking , When I think of someone at the cruel level . The following is an inductive analysis .

First of all, we use mathematical induction to analyze ：
1、 When only one plate is moved , We can determine the only action ： Direct the disc from from Move to to On .
2、 Now suppose you move n null , And we can finally move these discs to to On , Of course, you can also move to temp On （ It's just a hypothesis , This is the next proof of the inductive hypothesis ）
It can be easily proved that if n+1 We can also move all the discs to to On , Because we can put the above N Move to temp On （ The second step has been assumed ）, And then move the last one to to On , And then temp Move on to to On （ These assumptions have been made ）.
This may force us to prove by induction what
It is proved that a function can realize the Hanoi Tower problem , This Features of functions by ：
When the number of plates is 1 when , Directly to the 1 Execute move move(1,from,to) from from Move directly to to
If the number of plates is not n when , First the n-1 Move to temp, Then directly move the n Execute move move(n,from,to) from from Move directly to to, then temp Upper n-1 Move to to On .
First the n-1 Move to temp And Zaijiang temp Upper n-1 Move to to This is the same problem , Call your own function . Translate into Java The code is as follows , So simple ..

public void hanoi(int n,String from,String temp,String to){
    
	if(n==1){
    
		System.out.println(1+":"+from+"->"+to);
		return;
	}
	hanoi(n-1,from,to,temp);
	System.out.println(n+":"+from+"->"+to);
	hanoi(n-1,temp,from,to);
}

---

Factorial problem
This problem is also very difficult and easy if you use a loop

int n=6;// Assuming that 6 The factorial 
int a=1;
while(n>0){
    
	a=a*n;
	n--;
}

But here is the idea of recursive solution , Factorial algorithm is a typical case of thinking about small problem solving and merging into large problems , Taking the factorial of a number, it's easy to think of directly calculating from 1 Ride to n Work it out , If you can't figure it out, you've been trying to figure out how to get from 1 Ride to n, It's hard to jump out of the cycle of thinking and think n Factorials of and n-1 The factorial relation of the is solved recursively . In this case, you can imagine the relationship with the last factorial using recursion .
when 1 Time is directly 1
When it comes to 2 When is 12
When it comes to 3 When is 12*3
If n I know the factorial of
that n+1 The factorial of is multiplied by one n+1 Can , The recurrence equation comes out

public int factor(n){
    
	if(n==1)
		return 1;
	else
		return(n*factor(n-1));
}

Eliminate recursion

---

Recursion has advantages in analyzing problems , But the implementation based on recursion is not efficient , And because of the limitation of function stack size , The level of recursion is also limited . Eliminate recursion , In this way, recursive thinking can be adopted in the analysis phase , The non recursive algorithm is used in the implementation stage .
Recursion means turning a big problem into a small problem, solving a small problem first, then solving a larger problem on the basis of a small problem, and then solving a layer of big problems , If you can save the solution results of small problems, you can solve big problems without calling yourself , To eliminate recursion, some can be eliminated by looping , For example, the factorial implementation above , But generally, it is not allowed , Because if you can use a loop to implement it, you generally won't use recursion . Recursion is used because the recursion process can save the results of the previous step , That is to say, the code is concise because it is based on the previous work . If you save the results saved in the previous step in other ways, you won't need to call your own functions , Increase of efficiency , For example, the factorial above uses a variable in the loop to save the calculation result of the previous loop , To eliminate calling your own functions is to find a way to save the results of the previous step . Basically, the function calling system is based on the stack , Each call involves the following operations ：
At the beginning of the call ： Stack the return address and local variables .
At the end of the call ： Out of the stack and will be returned to the return address at the time of entering the stack
It is natural to think that we can also use stack to eliminate recursion . So when to put it on the stack and when to put it out , What does the stack hold ,
Let's see if we use the stack to eliminate recursion

// Data to store 
class Data{
    
    // Method parameter 
    private int n;
    Data(int n){
    
    	this.n=n;
    }
    public int getData(){
    
    	return n;
    }
}

// Stack 
Stack<Data> myStack = new Stack<>();
// The state machine implements the operation process 
    public static int execute(int num){
    
        int i = 1;   
        int result = 1;
        while(i!=6){
           // end 
            switch(i){
    
                case 1:     // initialization 
                    i=2;
                    break;
                case 2:     // Whether the condition ends 
                    if(num==1){
    
                        result=1;
                        i=4;
                    }else{
    
                        i=3;
                    }
                    break;
                case 3:     // Recursive stack 
                    Data data = new Data(num);
                    myStack.push(data);
                    num--;   // Conditions change 
                    i=2;
                    break;
                case 4:     // Whether the stack is empty 
                    if(myStack.isEmpty()){
    
                        i=6;
                    }else{
    
                        i=5;
                    }
                    break;
                case 5:     // Backtracking the stack 
                    Data data1 = myStack.pop();
                    result*=data1.getData();
                    i=4;
                    break;
                }
        }
        return result;
    }

Obviously, just imitate the calling process of the function , The idea of recursion is just that the implementation method changes from calling functions to stack entry and exit and execution jump , Answer the questions above , The parameters of the current environment, including variables and execution location, are pushed into the stack , Change the environment parameters after the stack The following uses the recursive idea to realize the Hanoi Tower problem without calling itself , The marking is clear and can be executed directly .

import java.util.Stack;

/** *  Here, pages are used to represent the data items in each stack  *  Every time I enter the stack , It is equivalent to turning the page once , As easy to understand as a Book  *  Every time I leave the stack, I will turn back the book  *  When you want to go to the next page , Save the current page information first , Enter again  *  The page information before the stack will pop up , Change the current parameter  * *  This kind of imagination is easy to understand , In fact, the so-called page turning is just the change of parameters  *  It's better to say what the parameters become when the page turns , It's just not easy to understand  *  Different pages show different parameters , The unique representation of the page can be num namely n Express  * * **/
class Hanoi{
    
	// Just to remember the steps , It's not about implementation 
	 int count=1;

	public static void main(String[]u){
    
		Hanoi han =new Hanoi();
		// This is implemented recursively , The comparison here is wrong , See if the non recursive result is correct 
		han.hanoi1(4,"A","B","C");
		System.out.println("-------------------");
		han.count=0;
		han.hanoi(4,"A","B","C");
	}
	class Data{
    
		private int num;   // Save page stack , Indicates which page you are currently on 
		private String from;  // Save the starting point of the current page to be moved 
		private String temp;// auxiliary 
		private String to;// Purpose 
		private int location;// Where does the current page go 
		Data(int n,String from,String temp,String to,int location){
    
			num=n;
			this.from=from;
			this.temp=temp;
			this.to=to;
			this.location=location;
		}

		public int getNum() {
    
			return num;
		}

		public String getFrom() {
    
			return from;
		}

		public String getTemp() {
    
			return temp;
		}

		public String getTo() {
    
			return to;
		}

		public int getLocation() {
    
			return location;
		}
	}

	public void hanoi1(int n,String from,String temp,String to){
    
		if(n==1){
    
			System.out.println(count+++"|"+1+":"+from+"->"+to);
			return;
		}
		hanoi1(n-1,from,to,temp);
		System.out.println(count+++"|"+n+":"+from+"->"+to);
		hanoi1(n-1,temp,from,to);
	}
	public void hanoi(int n,String from,String temp,String to){
    
		// Stack for storing page data 
		Stack<Data> myStack1 = new Stack<>();
		int i=1;// Used for state transition , That is to say, what steps should be performed 
		String temp1;
		while(i!=4){
    
			switch(i){
    
				case 1:
					if(n==1){
    
						// When it is the last page , That is, when there is only one disk , Just like the recursive part 
						System.out.println(count+++"||"+n+":"+from+"->"+to);
						i=3;// go to 3 It's about , That is, go to the pop-up stack , Return to the previous page 
					}
					else{
    
						// Otherwise go to 2, Continue to stack 
						i=2;
					}
					break;
				case 2:
					// Stack the current page information , Here we go to the first function 
					myStack1.push(new Data(n,from,temp,to,1));
					// After the current page information is stacked , Turn the page to the next page ,（ About to change parameters ）（ Equivalent to recursive hanoi1(n-1,from,to,temp);）
					n--;
					temp1=to;
					to=temp;
					temp=temp1;
					i=1;// Then go to another page, which is equivalent to recursively executing the function from the beginning 
					break;
				case 3:
					// An empty stack is the end 
					if (myStack1.isEmpty()){
    
						i=4;
						break;
					}
					else {
    
						// Turn back one page （ The pop-up page information is used to modify parameters ）
						Data data = myStack1.pop();
						// That is, the recursive execution to hanoi1(n-1,from,to,temp);
						if (data.getLocation()==1) {
    
							// Equivalent to recursive System.out.println(count+++"|"+n+":"+from+"->"+to);
							System.out.println(count+++"||"+data.getNum() + ":" + data.getFrom() + "->" + data.to);
							// Update parameters with information in the stack （ The parameter changes when the page is turned ）
							n=data.getNum();
							from = data.getFrom();
							temp = data.getTemp();
							to=data.getTo();
							// Execute to another function , Equivalent to executing into recursion hanoi1(n-1,temp,from,to);
							// Stack the current page information , It's different here from above , Because the implementation has reached a different place 
							myStack1.push(new Data(n, from, temp, to,2));
							// After the current page information is stacked , Turn the page to the next page ,（ About to change parameters ）（ Equivalent to recursive hanoi1(n-1,temp,from,to)）
							n--;
							temp1 = from;
							from = temp;
							temp = temp1;
							i = 1;// Then go to another page, which is equivalent to recursively executing the function from the beginning 
						}
						// If location==2 It means that the second function is executed when the stack is last loaded , End the current function directly , That is, pop up the stack of the previous page 
						else{
    
							i=3;
						}
						break;
					}
			}
		}
	}
}