Analysis on the use of Java recursive algorithm

Author：Eve Cole Update Time：2024-11-18 19:24:01

A recursive algorithm is an algorithm that calls itself directly or indirectly. In computer programming, recursive algorithms are very effective in solving a large class of problems. It often makes the description of the algorithm concise and easy to understand.

Question 1: The rules for a column of numbers are as follows: 1, 1, 2, 3, 5, 8, 13, 21, 34. What is the 30th digit? Use recursion to implement

Copy the code code as follows:

public class FibonacciSequence {
public static void main(String[] args){
System.out.println(Fribonacci(9));

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

}
}

Question 2: Tower of Hanoi problem

The Tower of Hanoi (also known as the Tower of Hanoi) is actually an ancient legend in India.

Brahma, the god who created the world (a god similar to Pangu in China), left three diamond rods in a temple. The first one was covered with 64 round gold pieces, the largest one was at the bottom, and the other ones were smaller than A small one, stacked up one after another, and the monks in the temple moved them one by one from one stick to another. It is stipulated that the middle stick can be used as a help, but only one can be moved at a time. , and the big one cannot be placed on top of the small one. The calculation result is very scary (the number of times the disk is moved): 18446744073709551615. Even if the monks spend their entire lives, it is impossible to complete the movement of the gold disk.

Requirement: Enter a positive integer n, indicating that there are n disks on the first pillar. Output the sequence of operations in the format of "move t from x to y". Each operation has one line, which means moving the disk numbered t on column x to column y. The columns are numbered A, B, and C. You need to transfer all the plates from column A to column C with the least amount of operations.

Copy the code code as follows:

public class Hanio {
public static void main(String[] args){
int i=3;
char a ='A',b='B',c='C';
hanio(i,a,b,c);
}
public static void hanio(int n,char a,char b,char c){
if(n==1)
System.out.println("Move plate "+n+" from "+a+" to "+c");
else{
hanio(n-1,a,c,b);//Move the above n-1 plates from a to c with the help of b
System.out.println("Move plate "+n+" from "+a+" to "+c");//Then move n directly to c
hanio(n-1,b,a,c);//Move n-1 plates on b to c with the help of a
}
}
}