Abstract:
Master L. Peter Deutsch said: To Iterate is Human, To Recurse, Divine. Man understands iteration, god understands recursion. Recursion is, of course, a wonderful way of thinking. For some simple recursive problems, we are always amazed at the ability of recursion to describe the problem and the simplicity of coding, but it is not easy to really understand the essence of recursion and flexibly use recursion to solve the problem. This paper analyzes the ideological connotation of recursion, analyzes the connection and difference between recursion and circulation, and gives the application scenarios and some typical applications of recursion. Eight classical problems including factorial, Fibonacci sequence, Hannotta, access to Yang Hui’s triangle, string palindrome judgment, string full arrangement, binary search and tree depth solution are solved by recursive and non-recursive methods.
Copyright Notice:
In this paper, the original author: nerd Rico author’s blog: blog.csdn.net/justloveyou… Friendly tips:
If you need the full code for this blog post, please go to my Github project SwordtoOffer and link to github.com/githubofric… .
A tease.
Master L. Peter Deutsch said: To Iterate is Human, To Recurse, Divine. Man understands iteration, god understands recursion. Recursion is, of course, a wonderful way of thinking. For some simple recursive problems, we are always amazed at the ability of recursion to describe the problem and the simplicity of coding, but it is not easy to really understand the essence of recursion and flexibly use recursion to solve the problem. Before the formal introduction of recursion, we quoted first zhihu user ji-gang li (www.zhihu.com/question/20)… A vivid explanation of recursion and loops:
Recursion: You open the door in front of you and see another door in the room. You walk up to it and find that the key in your hand can still open it. You push the door open and find another door inside. You keep opening it. A few times later, you open the door in front of you and there is only one room, no door. Then you begin to retrace your steps, counting each time you return to a room. When you reach the entrance, you can answer how many doors you have opened with your key.
Loop: You open the door in front of you and see another door inside. You go to the door and find that the key in your hand can open it. You push the door open and find another door inside. (If the first two doors are the same, then this door is the same as the first two; If the second door is smaller than the first door, then this door is smaller than the second door, and you keep opening this door, and you keep doing this until you open all the doors. However, the person at the entrance can’t wait for you to come back and tell him the answer.
The above metaphor vividly illustrates the connotation of recursion and loop, so let’s consider the following questions: what is recursion? What is the essence (idea) of recursion? What’s the difference between recursion and loop? When should I use recursion? What do I need to know about recursion? What classical problems did recursion solve? These are exactly the questions that the author intends to elaborate on in this paper.
The connotation of recursion
1. Definition (What is recursion?)
In mathematics and computer science, Recursion is the use of the function itself in the definition of a function. In fact, recursion, as the name implies, has two meanings: recursion and return, which is the essence of the idea of recursion.
2. The essence of recursion (what is the essence of recursion?)
As in the scenario described above, recursion is going (recursion) and going (return), as shown below. It means that the recursive problem must be decomposed into several smaller sub-problems of the same form as the original problem, which can be solved by using the same idea, just as the key in the above example can unlock all the doors behind it. It means that these problems evolve from big to small, from near to far, and there is a definite end point (the tipping point), once reached, there is no need to go smaller and farther. Finally, starting at this critical point, the original path returns to the origin and the original problem is solved.
3. Understand recursion by induction
We’re not bad at math, and our first reaction is what is the mathematical model of recursion, because we’re much better at modeling problems mathematically than we are at modeling problems in code. If we look at recursion, we will find that the mathematical model of recursion is actually mathematical induction, which is the most commonly used in high school sequences, so let’s recall mathematical induction.
Mathematical induction is applicable to transform the original problem solved into its subproblem solved, and its subproblem becomes the subproblem of the subproblem, and we find that these problems are actually a model, that is to say, there are the same logical induction treatment terms. The one exception, of course, is that the end of the induction does not apply to our induction, nor does it, otherwise we would have infinite induction. In general, induction mainly contains the following three key elements:
Step expression: the expression that transforms the problem into a subproblem End condition: When can the expression be solved directly without using step expression: In fact, this is why some mathematical sequence problems can be solved programmatically using recursion, such as the famous Fibonacci sequence problem.
4. Three elements of recursion
Now that we know the basic idea of recursion and its mathematical model, how can we write a beautiful recursive program? The author thinks it is mainly to grasp the following three aspects:
//1. Specify the recursive termination condition;
//2.
//3. Extract repetitive logic and reduce the problem size.
Copy the code1). Clarify recursive termination conditions
As we know, recursion is something that goes back and forth, and in that case, there must be a definite point at which the program, once it reaches that point, doesn’t keep going down and actually starts coming back. In other words, the critical point is a simple situation that prevents infinite recursion.
2). The treatment method of recursive termination is given
We just said that there is a simple case at the recursive tipping point, and in that simple case, we should just give the solution to the problem. Generally, in this situation, the solution to the problem is straightforward and easy.
3). Extract repetitive logic and reduce the problem size *
When we expound the connotation of recursion, we say that the recursion problem must be decomposed into several smaller sub-problems with the same form as the original problem, and these sub-problems can be solved by the same way of thinking. From a program implementation point of view, we need to abstract out a clean repeating logic to solve subproblems in the same way.
5,A recursive algorithmProgramming model of
Now that we’ve identified the three elements of recursive algorithm design, it’s time to start writing concrete algorithms. In writing the algorithm, without loss of generality, we give two typical recursive algorithm design models, as shown below.
Model 1: Solve the problem on the way
function recursion(On a large scale){ if (end_condition){
// Explicitly recursive terminating condition end;
// Simple scenario
}else{
// At each step of converting the problem into a subproblem, solve the remaining problems in that step.
// recursion(small); // Pass to the deepest, keep coming back}
}
Copy the codeModel 2: Solve problems on the way back
function recursion(On a large scale){
if (end_condition){
// Explicitly recursive terminating condition end;
// Simple scenario
}else{
Recursion (small scale); // Recursion (small scale);
/ / to solve;
/ / return}}Copy the code6. Application scenarios of recursion
In our actual learning work, recursive algorithms are generally used to solve three types of problems:
(1). The problem is defined recursively (Fibonacci function, factorial…). ;
(2) The solution of the problem is recursive (some problems can only be solved by recursive method, for example, Hannotta problem…) ;
(3). The data structure is recursive (operations of linked lists, trees, etc., including tree traversal, tree depth…). .
Below we will give some classic application cases of recursive algorithms, which basically fall into the category of the third type of problems.
Recursion and loop
Recursion and loop are two different typical approaches to problem solving. Recursion is usually a straightforward description of how a problem is solved, and is therefore the easiest way to think of a solution. Loops have the same properties as recursion in that they do repetitive tasks, but sometimes algorithms that use loops do not describe the steps to solve the problem as clearly as possible. In terms of algorithm design alone, recursion and loop are not superior or inferior. In practice, however, recursion often causes performance problems because of the overhead of function calls, especially if the solution size is uncertain; Loops are more efficient than recursion because they have no function call overhead. Recursion and loop are often interchangeable, meaning that loop substitution is usually good if it is easy to use recursion without affecting the reading of the program. Conversion of recursive implementation of the problem into non-recursive implementation generally requires two steps: (1). Build their own “stack (some local variables)” to store these contents in order to replace the system stack, such as three non-recursive traversal of the tree;
(2). Convert calls to recursion to loop processing.
In particular, we will give some classic application cases of recursive algorithms in the following article. For the realization of these cases, we will generally give two solutions, recursive and non-recursive, for readers to experience.
Four. Classical recursive problem combat
1. Problems of the first type: Problems are defined recursively
(1) factorial
/** * Title: implementation of factorial * Description: * recursive * non-recursive *@author rico* /
public class Factorial {
/ * * *@description Recursive implementation of factorial *@author rico
* @created May 10, 2017 8:45:48 PM *@param n
* @return * /
public static long f(int n){
if(n == 1) // Recursive termination condition
return 1; // Simple scenario
return n*f(n-1); // Repeat the same logic to reduce the size of the problem} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- I'm line -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --/ * * *@description A non-recursive implementation of factorial *@author rico
* @created May 10, 2017 8:46:43 PM *@param n
* @return * /
public static long f_loop(int n) {
long result = n;
while (n > 1) {
n--;
result = result * n;
}
returnresult; }}Copy the code(2). Fibonacci series
-
Title: Fibonacci sequence
-
Description: The Fibonacci sequence, also known as the Golden ratio sequence, refers to the sequence of numbers: 1, 1, 2, 3, 5, 8, 13, 21…
-
Mathematically, the Fibonacci sequence is defined recursively as follows: F0=0, F1=1, Fn=F(n-1)+F(n-2) (n >=2, n∈N*).
-
There are two recursive solutions: classical and optimal
-
There are two non-recursive solutions: recursion and array
* @author rico
*/
public class FibonacciSequence {
/ * * *@description Classic recursive method to solve the Fibonacci sequence is as follows: * * * * 1,1,2,3,5,8,13,21,34,... * * * Then, to calculate fib(5), fib(4), fib(3), fib(2), fib(1)* is called twice, i.e. * * fib (5) = fib (4) + fib * * fib (3) (4) = fib (3) + fib (2); Fib of 3 is equal to fib of 2 plus fib of 1 * * fib of 3 is equal to fib of 2 plus fib of 1 * * there's a lot of double counting going on, and we only have to compute fib of 4, fib of 3, fib of 2 and fib of 1, * The following optimizeFibonacci function is optimized to reduce the time complexity to O(n). * *@author rico
* @created May 10, 2017 12:00:42 PM *@param n
* @return* /
public static int fibonacci(int n) {
if (n == 1 || n == 2) { // Recursive termination condition
return 1; // Simple scenario
}
return fibonacci(n - 1) + fibonacci(n - 2); // Repeat the same logic to reduce the size of the problem
}
Copy the code/ * * *@description The optimization of classical recursive method the Fibonacci sequence is as follows: * * * * 1,1,2,3,5,8,13,21,34,... * * Well, we can look at it this way: Fib (1,1,5) = fib(1,2,4) = fib(2,3,3) = 5 * * so the fifth entry in the Fibonacci sequence starting with 1,1 is the fourth entry in the Fibonacci sequence starting with 1,2, * the fourth entry in the Fibonacci sequence starting with 1,2 is the third entry in the Fibonacci sequence starting with 2,3. * more directly, we can do it in one step: fib(2,3,3) = 2 + 3 = 5, and the calculation is complete. * * Note that the first two arguments are the first two entries in the sequence, and the third argument is the number of entries in the sequence that we want to find. *Copy the code* Time complexity: O(n) * * @author Rico * @param first item * @param second item * @param n target item * @return
*/
public static int optimizeFibonacci(int first, int second, int n) {
if (n > 0) {
if(n == 1) {// Recursive termination condition
return first; // Simple scenario
}else if(n == 2) {// Recursive termination condition
return second; // Simple scenario
}else if (n == 3) { // Recursive termination condition
return first + second; // Simple scenario
}
return optimizeFibonacci(second, first + second, n - 1); // Repeat the same logic to reduce the size of the problem
}
return -1; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- I'm line -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --/ * * *@description Non-recursive solution: there is no return@author rico
* @created May 10, 2017 12:03:04 PM *@param n
* @return* /
public static int fibonacci_loop(int n) {
if (n == 1 || n == 2) {
return 1;
}
int result = -1;
int first = 1; // self-maintained "stack" for state backtracking
int second = 1; // self-maintained "stack" for state backtracking
for (int i = 3; i <= n; i++) { / / loop
result = first + second;
first = second;
second = result;
}
returnresult; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- I'm line -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --/ * * *@description Use arrays to store Fibonacci numbers@author rico
* @param n
* @return * /
public static int fibonacci_array(int n) {
if (n > 0) {
int[] arr = new int[n]; // Use temporary arrays to store Fibonacci numbers
arr[0] = arr[1] = 1;
for (int i = 2; i < n; i++) { // Assign to a temporary array
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n - 1];
}
return -1; }}Copy the code(3). The value of Yang Hui triangle
/ * * *@description Recursively retrieves the value of the specified row and column (starting from 0) of the Triangle@author rico
* @x Specify rows *@y The specified column * /
/** ** Title: The Yang Triangle is also called Pascal triangle, whose I +1 row is the coefficient of the expansion of (a+b) I. * One of its important properties is that each number in a triangle is equal to the sum of the numbers on its two shoulders. * * For example, the first four rows of the Yang Hui triangle are given below: * 1 * 1 1 * 1 2 1 * 1 3 3 1 *@description Recursively retrieves the value of the specified row and column (starting from 0) of the Triangle@author rico
* @x Specify rows *@y The specified column * /
public static int getValue(int x, int y) {
if(y <= x && y >= 0) {if(y == 0 || x == y){ // Recursive termination condition
return 1;
}else{
// Call recursively to reduce the size of the problem
return getValue(x-1, y-1) + getValue(x-1, y); }}return -1; }}Copy the code(4) judgment of palindrome string
- Title: Judgment of palindrome string
- Description: A palindrome string is a string that reads the same backwards and forwards. For example, “98789”, “abccba” are palindrome strings
- There are two solutions:
- Recursive judgment;
- Cyclic judgment;
* @author rico
*/
public class PalindromeString {
/ * * *@description Recursively determines whether a string is a palindrome string *@author rico
* @created May 10, 2017 5:45:50 PM *@param s
* @return * /
public static boolean isPalindromeString_recursive(String s){
int start = 0;
int end = s.length()-1;
if(end > start){ // Recursive terminating condition: two Pointers move towards each other. When start exceeds end, the judgment is completed
if(s.charAt(start) ! = s.charAt(end)){return false;
}else{
// Call recursively to reduce the size of the problem
return isPalindromeString_recursive(s.substring(start+1).substring(0, end-1)); }}return true; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- I'm line -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --/ * * *@description Loop through the palindrome string *@author rico
* @param s
* @return * /
public static boolean isPalindromeString_loop(String s){
char[] str = s.toCharArray();
int start = 0;
int end = str.length-1;
while(end > start){ // Loop termination condition: two Pointers move towards each other. When start exceeds end, the judgment is completed
if(str[end] ! = str[start]){return false;
}else{ end --; start ++; }}return true; }}Copy the code(5). Full array of strings
The recursive method
- @description picks one element at a time from the string array as the first element in the result; And then you arrange the rest of the elements
* @author Rico * @param s * character array * @paramfrom* start subscript * @param to * end subscript */ publicstatic void getStringPermutations3(char[] s, int from, int to) {
if(s ! =null && to >= from && to < s.length && from> =0) { // Boundary condition check
if (from == to) { // Recursive termination condition
System.out.println(s); // Print the result
} else {
for (int i = from; i <= to; i++) {
swap(s, i, from); // Swap prefixes as the first element in the result, and then arrange the rest of the elements
getStringPermutations3(s, from + 1, to); // Call recursively to reduce the size of the problem
swap(s, from, i); // Replace the prefix to restore the character array}}}}/ * * *@description Swaps the specified characters in the character array *@author rico
* @param s
* @param from
* @param to* /
public static void swap(char[] s, int from, int to) {
char temp = s[from];
s[from] = s[to];
s[to] = temp;
}
Copy the codeNon-recursive solution (lexicographic complete arrangement)
-
Title: String full permutation non-recursive algorithm (lexicographic full permutation)
-
Description: Lexicographical complete order, the basic idea is:
-
First, the strings that need to be sorted are sorted lexicographically, that is, the smallest permutation of all permutations is obtained.
-
Then, find the smallest total permutation larger than it, and repeat this step until you find the maximum, which is the reverse of the lexicographic sort.
-
You don’t care about the string length
-
@author rico
-
public class StringPermutationsLoop {undefined
/ * * *@description Lexicographical permutations * * Let a string (array of characters) have n permutations A1,A2,A3... 1. Find the smallest permutation Ai * 2. Find the smallest successor permutation Ai+1 * 3. Repeat the previous step until there is no such successor * * The key is to find a permutation of the immediate successor: * for the string (character array) a0A1A2...... Ai +1 = ai+1; ai+1 = ai+1; ai+1 = ai+1; ai+1 = ai+1; * 2. Select aj (minMax = j) from top (including top). * 3. Swap characters at minMax and top-1; * 4. Invert the characters after top (including top) to obtain a direct successor to the permutation *Copy the code* @author Rico * @param s * character array * @paramfrom* start subscript * @param to * end subscript */ publicstatic void getStringPermutations4(char[] s, int from, int to) {
Arrays.sort(s,from,to+1); // Order all the elements of the character array in ascending order, that is, to get the minimum order
System.out.println(s);
char[] descendArr = getMaxPermutation(s, from, to); // Get the maximum permutation, that is, the inverse of the minimum permutation
while(! Arrays.equals(s, descendArr)) {// Loop terminating condition: iterate to maximum permutation
if(s ! =null && to >= from && to < s.length && from> =0) { // Boundary condition check
int top = getExtremum(s, from, to); // Find the extreme value of the sequence
int minMax = getMinMax(s, top, to); // Find the minimum value greater than s[top-1] from top (including top)
swap(s, top - 1, minMax); // Swap minMax and top-1 characters
s = reverse(s, top, to); // Invert the characters after topSystem.out.println(s); }}}/ * * *@description Swaps the specified characters in the character array *@author rico
* @param s
* @param from
* @param to* /
public static void swap(char[] s, int from, int to) {
char temp = s[from];
s[from] = s[to];
s[to] = temp;
}
/ * * *@description Gets the extreme value of the sequence *@author rico
* @param * s sequence@param From start subscript *@param To terminates the subscript *@return * /
public static int getExtremum(char[] s, int from, int to) {
int index = 0;
for (int i = to; i > from; i--) {
if (s[i] > s[i - 1]) {
index = i;
break; }}return index;
}
/ * * *@description Find from top the minimum value greater than s[top-1] *@author rico
* @created May 10, 2017 9:21:13 am *@param s
* @param Top Indicates the maximum value *@param to
* @return * /
public static int getMinMax(char[] s, int top, int to) {
int index = top;
char base = s[top-1];
char temp = s[top];
for (int i = top + 1; i <= to; i++) {
if (s[i] > base && s[i] < temp) {
temp = s[i];
index = i;
}
continue;
}
return index;
}
/ * * *@description Flip the sequence after top(including top) *@author rico
* @param s
* @param from
* @param to
* @return * /
public static char[] reverse(char[] s, int top, int to) {
char temp;
while(top < to){
temp = s[top];
s[top] = s[to];
s[to] = temp;
top ++;
to --;
}
return s;
}
/ * * *@description The maximum permutation * is obtained from the minimum permutation@author rico
* @param Minimum order of s *@param From start subscript *@param To terminates the subscript *@return * /
public static char[] getMaxPermutation(char[] s, int from, int to) {
// Copy the smallest permutation into a new array
char[] dsc = Arrays.copyOfRange(s, 0, s.length);
int first = from;
int end = to;
while(end > first){ // Loop termination condition
char temp = dsc[first];
dsc[first] = dsc[end];
dsc[end] = temp;
first ++;
end --;
}
return dsc;
}
Copy the code(6) binary search
- @description a recursive implementation of binary lookup
- @author rico
- @param array Target array
- @param low Left margin
- @param high Right boundary
- @param target Target value
- @return Location of the target value
public static int binarySearch(int[] array, int low, int high, int target) {
// Recursive termination condition
if(low <= high){
int mid = (low + high) >> 1;
if(array[mid] == target){
return mid + 1; // Returns the position of the target value, starting at 1
}else if(array[mid] > target){
// Array [mid] is not the target value, so it can be excluded from the recursive search
return binarySearch(array, low, mid-1, target);
}else{
// Array [mid] is not the target value, so it can be excluded from the recursive search
return binarySearch(array, mid+1, high, target); }}return -1; // Indicates that no search is found} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- I'm line -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --/ * * *@description A non-recursive implementation of binary lookup *@author rico
* @param Array Target array *@param Low Left margin *@param High Right border *@param Target Target value *@return Target value location */
public static int binarySearchNoRecursive(int[] array, int low, int high, int target) {
/ / loop
while (low <= high) {
int mid = (low + high) >> 1;
if (array[mid] == target) {
return mid + 1; // Returns the position of the target value, starting at 1
} else if (array[mid] > target) {
// Array [mid] is not the target value, so it can be excluded from the recursive search
high = mid -1;
} else {
// Array [mid] is not the target value, so it can be excluded from the recursive search
low = mid + 1; }}return -1; // Indicates that no search is found
}
Copy the code2. The second type of problem: the problem solution is realized by recursive algorithm
(1). Hannotta problem
- Title: Hannotta problem
- Description: In ancient times, there was A Vatican pagoda with three plates A, B and C. There were 64 plates in block A. The plates were of different sizes.
- A monk wanted to move the 64 plates from Block A to Block C, but he was allowed to move only one plate at A time, and in the process, the plates in the three blocks should always remain below the plate.
- Small plate on top. B seat can be used during movement. Input the number of layers, and output how each step is moved.
* @author rico
*/
public class HanoiTower {
/ * * *@description In the program, we call the top plate the first plate and the bottom plate the NTH plate *@author rico
* @param Level: number of plates *@param From Initial address of the plate *@param Inter is used to transfer plates *@param To the destination address of the dish */
public static void moveDish(int level, char from, char inter, char to) {
if (level == 1) { // Recursive termination condition
System.out.println("From" + from + "Move the plate" + level + " 号到" + to);
} else {
// Recursive call: Move level-1 plates from FROM to Inter (not at once, only one plate can be moved at a time, where to is used for turnover)
moveDish(level - 1.from, to, inter); // Call recursively to reduce the size of the problem
// Move the level plate from A to C
System.out.println("From" + from + "Move the plate" + level + " 号到" + to);
// Recursive calls: Move level-1 dishes from inter to FROM for turnover
moveDish(level - 1, inter, from, to); // Call recursively to reduce the size of the problem
}
}
public static void main(String[] args) {
int nDisks = 30;
moveDish(nDisks, 'A'.'B'.'C');
}
Copy the code3. Third problem: The structure of the data is defined recursively
(1). Binary tree depth
- Title: Recursively solves the depth of a binary tree
- Description:
- @author rico
- @Created May 8, 2017 6:34:50 PM
public class BinaryTreeDepth {
/ * * *@description Returns the depth of a binary number *@author rico
* @param t
* @return * /
public static int getTreeDepth(Tree t) {
/ / tree is empty
if (t == null) // Recursive termination condition
return 0;
int left = getTreeDepth(t.left); // Find the left subtree depth recursively, reduce the size of the problem
int right = getTreeDepth(t.left); // Find the right subtree depth recursively, reduce the size of the problem
return left > right ? left + 1 : right + 1; }}Copy the code(2). Binary tree depth
- @description preorder traversal (recursive)
- @author rico
- @Created May 22, 2017 3:06:11 PM
- @param root
- @return
public String preOrder(Node<E> root) {
StringBuilder sb = new StringBuilder(); // To the recursive call stack
if (root == null) { // Recursive termination condition
return ""; // ji
}else { // Recursive termination condition
sb.append(root.data + ""); // Traverses the current node in sequence
sb.append(preOrder(root.left)); // Preorder traverses the left subtree
sb.append(preOrder(root.right)); // Traverses the right subtree
returnsb.toString(); }}Copy the code