Deep understanding of Java recursion

One, recursive function, commonly said is the function itself to call their own...

Such as: n! = n (n - 1)!
You define f of n to be equal to nf of n minus 1.

And f of n minus 1 is a function of this definition. That's recursion

Why recursion: the purpose of recursion is to simplify the programming and make the program easy to read

Third, the drawback of recursion: although the non-recursive function is efficient, but more difficult to program, readability is poor. The downside of recursive functions is that they add overhead, meaning that each time you recurse, the stack takes up an extra chunk of memory

Iv. Recursion conditions: there should be a statement to complete the task, and the requirement of recursion should be satisfied (decrease rather than diverge).

V. recursive progression:
1. Calculate n factorial recursively:

  Analysis: n! = n * (n - 1) * (n - 2)... * 1

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

2. Use the recursive function to calculate the sum from 1 to n: 1+2+3+4+.. + n

 public int dReturn(int n){ 
  if(n==1){ 
   return 1; 
  }else{ 
   return n+dReturn(n-1); 
  } 
 } 

3. Require the output of a sequence: 1,1,2,3,5,8,11... (each number is the sum of the first two Numbers, the recursive function is required.)
  Java recursion to represent a function :F(n)=F(n-1)+F(n-2); F (0) = 1; F (1) = 1;
    Analysis: the X1 = 1; X2 = 1; The X3 = X1 + X2; X4 = X2 + X3; . ; Xn = X (n - 1) + X (n - 2)

  public int F(int n){ 
  if(n==1){ 
   return 1; 
  }else if(n==2){ 
   return 1; 
  }else{ 
    return F(n-1)+F(n-2); 
  } 
 } 

4. Java recursively reverse-prints the elements of an array of integers

  public static void printAll(int index,int[] arr){ 
   System.out.println(arr[index]); 
   if(index > 0){ 
    printAll(--index,arr); 
   } 
  } 
  public static void main(String[] args){ 
   int[] arr={1,2,3,4,5}; 
   printAll(arr.lenth-1,arr); 
  } 

5. Programming solution: if a heifer has a cow every year since the fourth year of birth, how many cows are there in the NTH year according to the rule of times?

  public static int cattle(int n){ 
if(n<=0){ 
 return 0; 
}else if(n<=3){ 
 return 1; 
}else{ 
 return cattle(n-1)+cattle(n-3); 
} 
  } 
  public static void main(String[] args){ 
   int n=10; 
   System.out.println(n+" After a total of "+cattle(n)+" Head of cattle "); 
  } 

Recursion, linear recursion, tail recursion?

Recursive function calls in Java - take the factorial of a number

Don't worry about overflows: it's usually just 69 factorial...

Note: 0 factorial 0! = 1

N factorial of any natural number greater than 1:
N! = 1 x 2 x 3 x... X n
Or n! = n * (n - 1)!
Search 0 factorial, can come out of an online calculator, very practical!!

package test;

import java.util.Scanner;

public class DiGui {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(" Enter an integer: ");
		Scanner scan = new Scanner(System.in);
		int x = scan.nextInt();
		int result = digui(x);
		System.out.println(result);
	}
	
	//Recursive function
	public static int digui(int x){
		if(x<=0){
			return 1;
		}else{
			return x*digui(x-1);
		}
	}
}

Recursion: a method by which a procedure or function directly or indirectly calls itself in its definition or specification, usually by transforming a large and complex problem into a smaller problem similar to the original one. This example clearly illustrates how recursion can turn a complex problem into a smaller problem. Here is a small example of how recursion works.

public class Test {
  static int multiply(int n) {
    int factorial; // ?? 

    if ((n == 1) || (n == 0)) {
      factorial = n;
    } else {
      factorial = n * multiply(n - 1);
    }

    return factorial;
  }

  public static void main(String[] args) {
    System.out.println(multiply(5));
  }
}

When a function is called, its variable space is created on the runtime stack. The variables of the previously called function are left on the stack, but they are hidden by the variables of the new function and therefore cannot be accessed.
The function in the program has two variables: the argument n and the local factorial. The following figures show the state of the stack, with currently accessible variables at the top of the stack. All other called variables are shaded in gray to indicate that they cannot be accessed by the currently executing function.
Suppose we call the recursive function with a value of 5. The contents of the stack are as follows, with the top of the stack at the bottom:

n multiply(n) factorial 
5 multiply(5) 5*multiply(4) //First call
4 multiply(4) 4*multiply(3) //Second call
3 multiply(3) 3*multiply(2) //Third call
2 multiply(2) 2*multiply(1) //Fourth call
1 multiply(1) 1 // Fifth call  

From the above information it is easy to see how recursion can be solved by minimizing a problem, starting with the method call, the factorial result will be pushed onto the stack until the method call ends, and then returned one by one from the top of the stack. After substitution one by one, the results are as follows:
N =1, 1 goes up 1
N =2 2*multiply(1) returns 2*1=2
N =3 3*multiply(2) up to return 3*(2*1)=6
N =4 4*multiply(3) up to return 4*(3*(2*1))=24
N =5 5*multiply(4) up to return 5*(4*(3*(2*1)))=120
Note: because multiply(1) or multiply(0) returns a value of 1
So 2 times multiply(1) is 2 times 1, which is 2
And since multiply(2) is recursive, it can be converted to 2*multiply(1).
So 3*multiply(2)=3*(2*multiply(1) =3*(2*1)=6
Because multiply(3) recurses to 3 times multiply(2)
Multiply so multiply (4) = 4 * (3) = 4 * 3 * (multiply) (2) = 4 * (3) * (2 * 1) = 24
Multiply (5)=5*multiply(4)
Can be reduced to 5 * 4 * (multiply) (3) = 5 * (4 * 3 * (multiply (2))) = 5 * (4 * (3) * (2 * 1)) = 120
Now let's look at the bytecode information:

public class Test extends java.lang.Object{ 
public Test(); 
Code: 
0: aload_0 
1: invokespecial #1; //Method java/lang/Object."<init>":()V 
4: return 
static int multiply(int); 
Code: 
0: iload_0 
1: iconst_1 //Push the int type constant 1 onto the stack
2: if_icmpeq 9 //If two values of type int are compared and equal, it jumps to position 9, which is the short-circuit function of | and |
5: iload_0 //Here, if the first condition fails, load an int from the local variable 0 (push the value of n)
6: ifne 14 //Compare, jump to position 14 if not equal to 0, note: since the default here is to compare with 0, there is no need to push the constant 0 on the stack
9: iload_0 //If there is no jump at ifne, load an int from local variable 0 (push the value of n)
10: istore_1 //Store values of type int in local variable 1 (the value that pops up at the top of the stack is the value that local variable 0 pushes on the stack, and then stores it in local variable 1)
11: goto 23 //Unconditional jump to position 23
14: iload_0 //Comparison at position 6, if not equal to 0 execute this instruction to load an int value (push the value of n) from the local variable 0
15: iload_0 //Load an int value from the local variable 0 (push the value of n)
16: iconst_1 //Push an int constant of type 1, which is 1 of n-1 in the code
17: isub //I'm subtracting, n minus 1
18: invokestatic #2; //Method multiply:(I)I, call Method multiply
21: imul //Multiply, n * multiply(n - 1)
22: istore_1 //Store the value of type int in the local variable 1, factorial=...
23: iload_1 //Load the value of type int from the local variable 1 (push the result of factorial onto the stack)
24: ireturn //Method returns
public static void main(java.lang.String[]); 
Code: 
0: getstatic #3; //Field java/lang/System.out:Ljava/io/PrintStream; 
3: iconst_5 
4: invokestatic #2; //Method multiply:(I)I 
7: invokevirtual #4; //Method java/io/PrintStream.println:(I)V 
10: return 
}