Shulou(Shulou.com)06/02 Report--

This article is about how to use recursive algorithms in Java. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

1. The definition of recursion

Recursion is to call yourself in the process of running.

Recursion must have three elements:

①, boundary condition

②, Recursive forward segment

③, recursive return segment

When the boundary condition is not satisfied, the recursive forward; when the boundary condition is satisfied, the recursive return.

2. Find the factorial of a number: n!

Stipulate that:

① 、 0! , 1

② 、 1! , 1

③, negative numbers have no factorial

Let's first rewrite the above expression with a for loop:

/ * * 0! = 1 1! = 1 * negative numbers have no factorial, if negative numbers return-1 * @ param n * @ return * / public static int getFactorialFor (int n) {int temp = 1; if (n > = 0) {for (int I = 1; I = 0) {if (n + "! = 1"); return 1;} else {System.out.println (n) Int temp = n*getFactorial (nMel 1); System.out.println (n + "! =" + temp); return temp;}} return-1;}

We call the method getFactorial (4); that is, 4! Print as follows:

When the boundary condition of this recursive program is nicked zero, 1 is returned. The specific calling procedure is as follows:

3. Recursive binary search

Note: the array of binary search must be orderly!

In the ordered array array [], the mid of the array is constantly compared with the value being looked up, and if the found value is equal to array [mid], the subscript mid; is returned. Otherwise, the search scope is halved. If the value being looked up is less than array [mid], continue to look on the left side; if the value being found is greater than array [mid], continue to look on the right side. The search ends until the value is found or the search scope is empty.

The binary search that does not need recursion is as follows:

/ * param array * @ param key * @ return * / public static int findTwoPoint (int [] array,int key) {int start = 0; int last = array.length-1; while (start array [mid]) {/ / the search value is larger than the current value start = mid+1;} if (key)

< array[mid]){//查找值比当前值小 last = mid-1; } } return -1;} 二分查找用递归来改写，相信也很简单。边界条件是找到当前值，或者查找范围为空。否则每一次查找都将范围缩小一半。 public static int search(int[] array,int key,int low,int high){ int mid = (high-low)/2+low; if(key == array[mid]){//查找值等于当前值，返回数组下标 return mid; }else if(low >

High) {/ / cannot find the lookup value and returns-1 return-1;} else {if (key)

< array[mid]){//查找值比当前值小 return search(array,key,low,mid-1); } if(key >

Array [mid]) {/ / lookup value is larger than the current value return search (array,key,mid+1,high);}} return-1;}

The efficiency of recursive binary search and non-recursive binary search is O (logN). Recursive binary search is more concise and easy to understand, but the speed is slower than that of non-recursive binary search.

4. Divide and conquer algorithm

When we solve some problems, because these problems have a lot of data to deal with, or the process of solving them is very complex, the direct solution takes a long time, or it is impossible to solve them directly at all. For this kind of problem, we often decompose it into several sub-problems, find the solution of these sub-problems, and then find a suitable method to combine them into the solution of the whole problem. If these sub-problems are still large and difficult to solve, they can be divided into several smaller sub-problems, and so on, until the solution can be solved directly. This is the basic idea of the divide and conquer strategy.

The recursive binary search method mentioned above is a typical example of a divide-and-conquer algorithm. The divide-and-conquer algorithm is often a method, in which there are two recursive calls to itself, corresponding to two parts of the problem.

In a binary search, the search range is divided into a part larger than the search value and a part smaller than the search value, and only one part of each recursive call is executed.

5. The problem of Hanoi Tower

The Tower of Hanoi problem is an ancient problem made up of many plates placed on three towers. As shown in the following picture, all the plates are of different diameters, and there is a hole in the center of the plate so that they can fit on the tower. All the plates were placed on Tower An at the beginning. The goal of this problem is to move all the plates from Tower A to Tower C, only one plate at a time, and no plate can be placed on a plate smaller than yourself.

Just imagine, if there are only two plates, and the plates are named after numbers from small to large (you can also imagine the diameter), on top of the two plates is plate 1, and below is plate 2, then we just need to move plate 1 to tower B. then move plate 2 to tower C, and finally move plate 1 to tower C. That is to complete the movement of 2 plates from A to C.

If there are three plates, then we put plate 1 on tower C, plate 2 on tower B, plate 1 of tower C on tower B, and plate 3 of tower An on tower C. then put plate 1 of tower B on tower A, plate 2 of tower B on tower C, and finally plate 1 of tower An on tower C.

If there are four, five, N plates, then what should we do? At this time, the idea of recursion is very good to solve this problem. When there are only two plates, we only need to use Tower B as an intermediary, first put plate 1 on intermediate tower B, and then put plate 2 on target tower C. finally, put the plate on intermediary tower B on target tower C.

So no matter how many plates there are, we think of them as only two plates. Suppose there are N plates on Tower A, and we think of them as two plates, of which (NMel 1) ~ 1 plate is regarded as a plate, and the bottom N plate is regarded as a plate, then the solution is:

①, first regard the first (Nmurl) ~ 1 plate of Tower An as a plate, put it on the intermediate tower B, and then put the Nth plate on the target tower C.

②, then tower An is empty and is regarded as an intermediary tower. At this time, tower B has a plate, and the first plate (Nmur2) ~ 1 is regarded as a plate, which is placed on the intermediate tower A, and then the No. 1 plate of tower B is placed on the target tower C.

③, at this time, there are 2 plates on Tower A, Tower B is empty, and Tower B is regarded as an intermediary tower. Repeat the ① and ② steps until all the plates are placed on the target tower C.

To put it simply, the recursive algorithm is the same as putting an elephant in the refrigerator:

①, move a plate containing nmur1 from the initial tower A to the intermediate tower B.

②, place the remaining plate on the initial tower A (the largest plate) on the target tower C.

③, move a plate from intermediary tower B to target tower C.

/ * * Hanoi Tower problem * @ param dish plates (also name) * @ param from initial tower * @ param temp intermediary tower * @ param to target tower * / public static void move (int dish,String from,String temp,String to) {if (dish = = 1) {System.out.println ("move plate" + dish+ "from tower" + from+ "to target tower" + to) } else {move (dish-1,from,to,temp); / An is the initial tower, B is the target tower, C is the intermediary tower System.out.println ("move the plate + dish+" from the tower "+ from+" to the target tower "+ to"); move (dish-1,temp,from,to); / / B is the initial tower, C is the target tower, An is the intermediary tower}}

Test:

Move (3, "A", "B", "C")

The print result is as follows:

6. Merge and sort

The center of the merging algorithm is merging two ordered arrays. Merge two ordered arrays An and B, and the third ordered array C is generated. Array C contains all the data items for arrays An and B.

The non-recursive algorithm is:

/ * pass in two ordered arrays an and b, and return a sorted merged array * @ param a * @ param b * @ return * / public static int [] sort (int [] aLint [] b) {int [] c = new int [a.length+b.length]; int aNum = 0m bNum = 0m cNumulative 0 While (aNum= b [bNum]) {/ / compare the elements of array an and array b, and who is smaller assigns to c array c [cNum++] = b [bNum++];} else {c [cNum++] = a [aNum++] }} / / if array an is all assigned to array c, but array b still has elements, then copy all the remaining elements of array b to array c while in order (aNum = = a.length & & bNum

< b.length){ c[cNum++] = b[bNum++]; } //如果b数组全部赋值到c数组了，但是a数组还有元素，则将a数组剩余元素按顺序全部复制到c数组 while(bNum == b.length && aNum < a.length){ c[cNum++] = a[aNum++]; } return c;} 该方法有三个while循环，第一个while比较数组a和数组b的元素，并将较小的赋值到数组c；第二个while循环当a数组所有元素都已经赋值到c数组之后，而b数组还有元素，那么直接把b数组剩余的元素赋值到c数组；第三个while循环则是b数组所有元素都已经赋值到c数组了，而a数组还有剩余元素，那么直接把a数组剩余的元素全部赋值到c数组。 归并排序的思想是把一个数组分成两半，排序每一半，然后用上面的sort()方法将数组的两半归并成为一个有序的数组。如何来为每一部分排序呢？这里我们利用递归的思想： 把每一半都分为四分之一，对每个四分之一进行排序，然后把它们归并成一个有序的一半。类似的，如何给每个四分之一数组排序呢？把每个四分之一分成八分之一，对每个八分之一进行排序，以此类推，反复的分割数组，直到得到的子数组是一个数据项，那这就是这个递归算法的边界值，也就是假定一个数据项的元素是有序的。　　 public static int[] mergeSort(int[] c,int start,int last){ if(last >

Start) {/ / can also be (start+last) / 2, so that it is written to prevent the addition of the two from exceeding the int range due to the large array length, resulting in overflow int mid = start+ (last-start) / 2; mergeSort (cMagne startMid); / / left array sort mergeSort (cMagneMid 1 last); / / right array sort merge (cMagne startLast) / / merge left and right array} return c;} public static void merge (int [] c temp int start,int mid,int last) {int [] temp = new int [last-start+1]; / / define temporary array int I = start;// define the left array subscript int j = mid + 1 stroke / define the right array subscript int k = 0; while (I = persons.length) {return } selects [index] = true; combination (teamNumber-1, index+1); selects [index] = false; combination (teamNumber, index+1);} public static void main (String [] args) {char [] persons = {'A','A', Thank you for your reading! This is the end of this article on "how to use recursive algorithms in Java". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.