Recursion is introduced

Recursion: the function calls itself. The subproblem must be the same thing as the original problem, or simpler; Recursion is usually easy to handle subproblems, but not always the best.

  • Call yourself
  • Recursion is usuallyDon't care about the operation, only care aboutThe initial conditionsandThe relationship between the upper and lower levels.
  • Recursive functionThere needs to be a critical stop pointThat is, recursion cannot continue indefinitely. Usually this point is a number that you have to go through.
  • Recursion can often be replaced by other alternatives (stack, array forward evaluation).

Recognize recursion. Recursive functions are usually simple but can be difficult for beginners to understand. Take a recursive function.

static void digui(a)
{
	System.out.println("Before the bigsai");
	digui();
	System.out.println("After bigsai");
}
Copy the code

Is it a recursion? It’s not normal recursion, there’s no end condition, it’s calling its own loop consistently. So the correct recursion would look like this

static void digui(int time)
{
	if(time==0) {}/ / time = = 0 does not perform
	else {
		System.out.println("Former bigsai time."+time);
		digui(time-1);
		System.out.println("After bigsai time."+time); }}Copy the code

For such a recursion, the execution flow looks something like this

Recursively take the factorial

O n! =n*(n-1)*—–*1=n! Is equal to n times n minus 1, so the relationship between the upper and lower levels of the factorial is easy to find. We assume that a function jiecheng(n) is a factorial function. This factorial, you could call it this way:

int jiecheng(int n)
{
   int va=1;
   for(inti=n; i>0; i--) { va*=i; }return i;
}
Copy the code

But you can also make it easy:

static int jiecheng(int n)
{
	if(n==0)//0 factorial is 1
	{
		return 1;
	}
	else {
		return n*jiecheng(n-1);//return n*(n-1)*jiecheng(n-2)=-------}}Copy the code

The running process is as follows:

Fibonacci recursively

Following the above thought, we assume that Fibonacci is F(n); First, Fibonacci’s formula is:

  • F[n]=F[n-1]+F[n-2](n>=3,F[1]=1,F[2]=1)
  • In other words, except for n=1 and n= 2, you can use recursion.

So the code for recursive implementation is:

static long F(int n)
{
	if(n==1||n==2) {return 1; }else {
		return F(n-1)+F(n-2); }}Copy the code

In fact, its call flow is as follows:

The meter
Matrix rapid power

Recursively solve Hanover tower

Hannotta is a classical recursive problem:

Legend has it that in ancient Indian temples, there was a game called Hanoi. The game is played on A copper plate device with three rods (numbered A, B and C), and 64 gold disks are placed from top to bottom on A rod (as shown below). The goal of the game: move all the gold disks on rod A to rod C, and still keep the original order of stacking. Operation rule: only one plate can be moved at A time, and in the process of moving, the big plate should always be kept on the bottom of the three rods, and the small plate should always be on the top. The plate can be placed on any of the rods A, B and C during the operation.

  1. If A has only one (A->C)
  2. If A has two (A-> B),(A->C), and (B->C)
  3. If A is three (A – > C), (A – > B), (C – > B), (A – > C), (B) – > A), (B) – > C), (A – > C).
  4. If there are more, it will explode.

You can see that every time you add a step, there are more steps. But think of it this way:

  • When one of them wants to go from A->C, and we know how to move it. Use a function to represent move (a->c). The same applies to other move operations.
  • ——-omitThe middle steps do not look, useRecursive thoughtSee a problem

Analysis: n from a — > C and n-1 a — > C are related? (Hannuo (n) — >hannuo(n-1) what does it matter?) Let’s say we have n plates

  • Hannuo (n-1) followed by n-1 plates from A — >C.
  • And then you’re left with the biggest one at the bottom, which can only move to B,move(A,B)
  • So did you find out anything,The transfer from C — >B can be completed with the same operation as the original Huannuo (N-1); So our previous function should be written ashannuo(n-1,A,C)But we’re using B again, so we pass in Bhannuo(n-1,A,B,C)First represented asN -1 from A(performing several operations with B) to C.
  • This sequence of operations takes n plates from A — >B, but what we want is A — >C. So we just need toChange the hannuo(n-1,----) orderIt is good!

After the above analysis, the complete operation is:

packageRecursion;public class hannuota {
	static void move(char a,char b)
	{
		System.out.println("Move the topmost."+ a+ "To"+ b+ "\t");
	}
	static void hannuota(int n,char a,char b,char c)// Analyze each step for the next step.
	{
		if(n==1) {move(a,c); }// Move from a to C
		else
		{
			hannuota(n-1,a,c,b);// Move n-1 from a to B with c
			move(a,c); // Move the NTH (last) from a to c.
			hannuota(n-1,b,a,c);// Move n-1 from b to C by a}}public static void main(String[] args)
	{
		
		hannuota(5.'a'.'b'.'c'); }}Copy the code

conclusion

In fact, recursion is inefficient in some scenarios. Fibonacci in particular. From the diagram you can see that a simple operation has many repetitions. Because it recursively calls both themselves. So its recursive inflation rate is exponential, repeating a lot of the same calculations. Of course, there are optimization solutions for this problem:

  • Table calculation from front to back, using the idea of similar dynamic programming. Think backwards. For example, Fibonacci F[n]=F[n-1]+F[n-2]; Then IStore in arrays. Let’s start with the third termF[3]=F[2]+F[1](all known), againF[4]=F[3]+F[2]—– thus, the time complexity is O(N), linear.
  • Of course, for factorial recursion, althoughTime is not reducedBut if need beMultiple accessA factorial, then you can use the same idea to solve the problem.

Finally, the author’s ability is limited, if the description is not appropriate, please correct, thanks to the previous dynamic graph (not found the original author) and hannota DYNAMIC graph open source author ISEA533 open source works. At the same time, if you like to learn and exchange welcome to pay attention to the author’s public number: BigSAI reply data structure presents a beautiful information!