1. Recursive functions, in layman's terms, means that the function itself calls itself...
Such as: n!=n(n-1)!
You define the function f(n)=nf(n-1)
And f(n-1) is a function of this definition. . This is recursion
2. Why use recursion: The purpose of recursion is to simplify program design and make the program easier to read.
3. Disadvantages of recursion: Although non-recursive functions are highly efficient, they are difficult to program and have poor readability. The disadvantage of recursive functions is that it increases system overhead. That is to say, every time it is recursed, the stack memory takes up more space.
4. Conditions for recursion: There must be a statement to complete the task, and the requirements for recursion must be met (reduce rather than diverge)
5. Recursive advancement:
1. Use recursion to calculate the factorial of n:
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 accumulation 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. It is required to output a sequence: 1,1,2,3,5,8,11... (each number is the sum of the previous two numbers, and a recursive function is required)
Use java recursion to represent a function: F(n)=F(n-1)+F(n-2);F(0)=1;F(1)=1;
Analysis: X1=1; X2=1; X3=X1+X2;
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 uses recursive method to reversely print each element in an integer array
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 gives birth to a cow every year starting from the fourth year after birth, how many cows are there in the nth year?
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+"There will be a total of "+cattle(n)+"cows" after the year); }What are the concepts of recursion, linear recursion, and tail recursion?
Calling recursive functions in Java - finding the factorial of a number
Overflow is not considered: generally only the factorial of 69 can be calculated...
Note: the factorial of 0 is 0! =1
The factorial representation of any natural number n greater than 1:
n!=1×2×3×……×n
Or n!=n×(n-1)!
Searching for the factorial of 0 will bring up an online calculator, which is very useful! !
package test;import java.util.Scanner;public class DiGui {public static void main(String[] args) {// TODO Auto-generated method stubSystem.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 process or function has a method of directly or indirectly calling itself in its definition or description. It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve. This case clearly illustrates how recursion can transform a complex problem into a smaller one to solve. The following is a small example to illustrate the principle of recursion.
/*** @fileName Test.java* @description ??????????* @date 2012-11-25* @time 17:30* @author wst*/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, space for its variables is created on the runtime stack. The variables of the previously called function remain on the stack, but they are obscured by the variables of the new function and therefore cannot be accessed.
The function in the program has two variables: parameter n and local variable factorial. The following diagrams show the state of the stack, with currently accessible variables at the top. All other called variables are shaded gray to indicate that they cannot be accessed by the currently executing function.
Suppose we call the recursive function with the value 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 ) //The third call 2 multiply(2) 2*multiply(1) //The fourth call 1 multiply(1) 1 //The fifth call
From the above information, it can be easily seen how recursion gradually minimizes a problem to solve it. Starting from the method call, the factorial results will be pushed onto the stack until the method call ends, and finally the results are returned one by one from the top of the stack. . After substitution one by one, the result is as follows:
n=1 1 returns 1 upwards
n=2 2*multiply(1) returns 2*1=2 upwards
n=3 3*multiply(2) returns 3*(2*1)=6 upwards
n=4 4*multiply(3) returns 4*(3*(2*1))=24 upwards
n=5 5*multiply(4) returns upward 5*(4*(3*(2*1)))=120
Note: Because multiply(1) or multiply(0) returns a value of 1
So there are 2*multiply(1)=2*1=2
And because multiply(2) meets the recursion condition, it can be transformed into 2*multiply(1) after recursion.
So there are 3*multiply(2)=3*(2*multiply(1))=3*(2*1)=6
Because multiply(3) can be reduced to 3*multiply(2) after recursion
So multiply(4)=4*multiply(3)=4*(3*multiply(2))=4*(3*(2*1))=24
By analogy, multiply(5)=5*multiply(4)
It can be reduced to 5*(4*multiply(3))=5*(4*3*(multiply(2)))=5*(4*(3*(2*1)))=120
Let’s take a 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 int type constant 1 onto stack 2: if_icmpeq 9 //Compare two int type values. If they are equal, jump to position 9. This is the short-circuit function of ||5: iload_0 //This is executed when the first condition does not hold, starting from local variable 0 Load an int type value (push the value of n onto the stack) 6: ifne 14 //Compare, if not equal to 0, jump to position 14. Note: Since the default here is compared with 0, there is no need to change the constant to 0 Push 9: iload_0 //If there is no jump at ifne, load the int type value from local variable 0 (push the value of n onto the stack) 10: istore_1 //Store the int type value into local variable 1 (pop the value on the top of the stack) That is, the value of local variable 0 is pushed onto the stack and then stored in local variable 1) 11: goto 23 //Unconditionally jump to position 23 14: iload_0 //Comparison at position 6, if it is not equal to 0, execute this instruction and load the int type value from local variable 0 (push the value of n onto the stack) 15: iload_0 //Load the int type value from local variable 0 (push the value of n onto the stack) Push the value of n onto the stack) 16: iconst_1 //Push the int type constant 1 onto the stack, the constant 1 is 1 of n-1 in the code 17: isub //Perform the subtraction operation, n-1 18: invokestatic #2; / /Method multiply:(I)I, call method multiply 21: imul //Perform multiplication operation, n * multiply(n - 1) 22: istore_1 //Store int type value in local variable 1, factorial=... 23: iload_1 //Load int type value from local variable 1 (push the result of factorial onto the stack) 24: ireturn //The 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 }