Detailed explanation of Java recursive algorithm (power node arrangement)

JavaRecursive algorithm is a recursive algorithm implemented based on Java language. Recursive algorithms are effective for solving a large class of problems, making the algorithm concise and easy to understand. Next, this article will introduce you to the knowledge about Java recursive algorithms. Friends who are interested can learn together.

The recursive algorithm is an algorithm that directly or indirectly calls its ownfunctionor method. Java recursive algorithm is a recursive algorithm implemented based on Java language. The essence of the recursive algorithm is to decompose the problem into sub-problems of the same type that are reduced in size, and then call methods recursively to represent the solution to the problem. Recursive algorithms are effective for solving a large class of problems, making the algorithm concise and easy to understand.

Features of recursive algorithm for solving problems:

1) Recursion is calling itself in the method.

2) When using the incremental recursion strategy, there must be a clear recursion end condition, called the recursion exit.

3) Recursive algorithm problem solving usually appears very simple, but the operating efficiency of recursive algorithm problem solving is low. Therefore, it is generally not recommended to use recursive algorithms to design programs.

4) 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.

The "repetition" embodied in the recursive algorithm generally has three requirements:

First, each call is reduced in scale ( Usually halved);

The second is that there is a close connection between two adjacent repetitions, and the previous one must be prepared for the next one (usually the output of the previous one is used as the input of the next one);

Third, when the scale of the problem is extremely small, the solution must be given directly instead of recursive calls. Therefore, each recursive call is conditional (provided that the scale does not reach the size of the direct answer), and unconditional recursion The call will become a dead loop and cannot end normally.

In order to understand the recursive algorithm, an example is given as follows:

Problem description:

Solve the Fibonacci sequence number The value of 10 positions? (Fibonacci Sequence (Fibonacci Sequence), also known as Golden Section Sequence, refers to such a sequence: 1, 1, 2, 3, 5, 8, 13, 21. ...In mathematics, the Fibonacci sequence is recursively defined as follows: F0=0, F1=1, Fn=F(n-1)+F(n-2) (n>=2 , n∈N*))

Java code list:

package com.bjpowernode.test; 
 
 public classFab { 
 
 public static void main(String args[]){ 
 System.out.println(fab(5)); 
 } 
 private static int fab(int index){ 
 if(index==1 || index==2){ 
  return 1; 
 }else{ 
  return fab(index-1)+fab(index-2); 
 } 
 } 
 }

Program analysis:

This example is a very classic example, mainly using Recursively implements the Fibonacci sequence. The exit of this recursive algorithm is in the code segment

 if(index==1 || index==2){ 
 return 1; 
 }

. If the index of the program meets the conditions, the recursion will stop. So the running process of this program is:

Up to this point in the program analysis, the recursive implementation is completed. Readers can simply make a demo to feel the algorithm. The subtlety, in fact, many people are saying that algorithms are difficult and difficult to reach the sky. In fact, mastering the root of the algorithm is the most important. What is the root of the algorithm? Take this recursive algorithm as an example. I feel that this root is that Exit, as long as you find the exit, the algorithm will naturally fall into place.

The above is the detailed content of Detailed explanation of Java recursive algorithm (power node arrangement). For more information, please follow other related articles on the PHP Chinese website!