How to create a simple example of java recursion

How to create java recursion: first create a clear recursion end condition; then set the judgment condition, the code is [private static int sumNum(int n){if (n == 1){return 1;}return n sumNum(n-1)}].

How to create java recursion:

The programming technique in which a program calls itself is called recursion. Recursion as an algorithm is widely used in programming languages. 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. The recursive strategy only A small number of programs are needed to describe the multiple repeated calculations required in the problem-solving process, which greatly reduces the amount of program code. The power of recursion lies in defining infinite collections of objects with finite statements. Generally speaking, recursion requires boundary conditions, a recursive forward segment, and a recursive return segment. When the boundary conditions are not met, the recursion advances; when the boundary conditions are met, the recursion returns.

First, let’s look at the simplest summation example.

<span style="font-size:18px;">public static void main(String[] args) {
System.out.println(sumNum(100)); //输出：5050
}
//求1-100的和
private static int sumNum(int n) {
if (n == 1) {
return 1;
}
return n + sumNum(n-1);
}</span>

Below we use recursion to implement the Fibonacci sequence.

The Fibonacci sequence, also known as the golden section sequence, refers to such a sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21,... In mathematics, Fibonacci The Bonacci sequence is recursively defined as follows: F(0)=0, F(1)=1, F(n)=F(n-1) F(n-2) (n≥2, n ∈N*) In modern physics, quasicrystal structure, chemistry and other fields, the Fibonacci sequence has direct applications.

//用递归求解
public static int fib(int n) {
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
return fib(n - 1) + fib(n - 2);
}
//用循环求解
public static int fib2(int n) {
int a = 0, b = 1, c = 1;
if (n == 0)
return 0;
if (n == 1 || n == 2)
return 1;
for (int i = 0; i < n - 1; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
//用数组求解
public static int fib3(int n) {
int[] arr = new int[n + 1];
arr[0] = 0;
arr[1] = 1;
for (int i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}

Let’s look at another example, calculating factorial.

Factorial is an arithmetic symbol invented by Christian Kramp (1760-1826) in 1808. It is a mathematical term.

The factorial of a positive integer (English: factorial) is the product of all positive integers less than and equal to the number, and the factorial of 0 is 1. The factorial of a natural number n is written n!. That is, n!=1×2×3×...×n. Factorial can also be defined recursively: 0!=1, n!=(n-1)!×n.

//用递归计算阶乘
public static int jc(int n)
{
//结束条件
if ( n == 1)
return 1;
//递归条件
return n * jc(n-1);
}
//用for循环实现阶乘
public static int jc2(int n)
{
int sum = 1;
for (int i = 1; i <= n; i++) {
sum *= i;
}
return sum;
}

Recursive conditions:

1. End condition: There must be a clear recursive end condition, called the recursive exit.

2. Recursive conditions: Recursive algorithm.

Characteristics of recursion:

1. Simple and clear: Recursive algorithm is generally easy to read at a glance It can be seen that the operation structure is very close to the natural language of mathematics.

2. High memory consumption: During the recursive call process, the system opens a stack to store the return points, local quantities, etc. of each layer. Too many recursions can easily cause stack overflow, etc. Therefore, it is generally not recommended to use recursive algorithms to design programs.

Related learning recommendations: java basic tutorial

The above is the detailed content of How to create a simple example of java recursion. For more information, please follow other related articles on the PHP Chinese website!