This series is my summary of data structure and algorithm when I was looking for a job many years ago. There are basic parts and classic interview questions of various companies. It was first published on CSDN. Is sorted out for a series of friends in need of reference, if there is a mistake, welcome to correct. The full code address for this series is here.
Note: I am writing this article on the rickety green train home from Guangzhou, which is full of homesickness and makes me want to read Zhou Yunpeng’s Green Train again. — Recorded at 22:00 p.m. on September 30, 2018.
0 overview
In front of the summary of random algorithm, this time to write the recursive algorithm before the article combing, this article is mainly inspired by the teacher Song Jinsong wrote “Linux C programming” recursive chapter. The most can reflect the essence of the algorithm is not recursion, I hope this article to learn recursion or recursion confused friends can help, if there is a mistake, also ask all the cattle correct. See the binary_tree directory in the repository for recursion examples of binary trees, and the rest of the code in this article.
A preliminary study on recursive algorithm
This section of content is mainly extracted from “Linux C one-stop programming”, the author is Song Jinsong teacher, this is I think currently see one of the best technical books on Linux C programming, strongly recommended!
A simple example of recursion is taking the factorial of integers, n! =n*(n-1)! , zero! = 1. The following recursive program can be written:
int factorial(int n)
{
if (n == 0)
return 1;
else {
int recurse = factorial(n-1);
int result = n * recurse;
returnresult; }}Copy the codeFactorial is a recursive function that calls itself. A recursive function is a function that calls itself directly or indirectly. If confused, think of the factorial(n-1) step as calling another function – another function with the same name and the same code – jumping into its code and then returning to the next step of the factorial(n-1) call.
To prove the correctness of the recursive algorithm, we can follow the results step by step. I remember when I just learned recursive algorithms, THERE is always a feeling of confusion, always thinking of recursion step by step to see the results of execution. It’s okay to have fewer levels of recursion, but if you have more levels of recursion, you have no idea what level of recursion you’re following. For example, factorial, if it’s just factorial of 3 that’s not a big problem, but if it’s factorial of 100 that’s really annoying.
In fact, we don’t need to follow every function to see the result. For example, when we call printf in our own function, we don’t drill in to see how it prints because we trust it to do the job. We write the factorial function as follows:
int recurse = factorial(n-1);
int result = n * recurse;
Copy the codeAt this point, if we believe factorial is correct, passing n-1 it will return n-1 factorial. , then the result = n * (n – 1)! =n! So this is factorial of n.
Of course this is a little odd: we haven’t written factorial yet, why should we believe factorial is correct? If you believe that the recursive function you are writing is correct, call it, and then write the recursive function based on that, then it will be correct and therefore worth believing that it is correct.
It’s a little tricky, but let’s prove factorial mathematically rigorously. Well, the correctness of factorial depends on the correctness of factorial of n-1, and as long as factorial is correct, there is no doubt that it will return the result multiplied by n, then our implementation is correct. So to prove factorial is to prove factorial of n-1, and in the same way to prove factorial of n-1 is to prove factorial of n-2, and so on, and so on, and so on, and finally: And to prove factorial of 1 is to prove factorial of 0. The correctness of factorial(0) does not depend on the other function call. It is a small branch of the program. This one that we wrote according to the definition of factorial, must be correct, so the implementation of factorial 1 is correct, so factorial 2 is correct, and so on, and factorial n is correct.
In fact, this is the mathematical induction that I learned in middle school. To prove by mathematical induction, I only need to prove two points: correct Base Case and correct recursion relationship. Remember to write Base Case when writing a recursive function, otherwise even if the recursion is correct, the whole function is not correct. If the factorial function misses the Base Case, it will loop indefinitely.
2. Recursive classical problems
From our discussion of a simple example of factorial in the previous section, we learned the essence of recursive algorithms: to understand functions functionally, you need to believe that the function you are writing is correct, call it on that basis, and it will be correct. So here’s how to understand recursion from a couple of common algorithms, and here’s what I think, and I welcome better ideas.
2.1) Hannotta problem
The hannott tower problem is A common problem in which n plates of different sizes are placed on top of tower A, in bottom-up order from largest to smallest. It is required that all n plates be moved to another tower C, with the aid of one tower B, but that large plates cannot be placed on small plates at any time.
Solution: The basic idea is to move n-1 plates from the top to B through C, then move the bottom plate to C, and then move n-1 plates from the top of B to C through A. The total time complexity f(n)=2f(n-1)+1, so f(n)=2 to the n-1.
/** ** / void hano(char a, char b, char c, int n) {if (n <= 0) return;
hano(a, c, b, n-1);
move(a, c);
hano(b, a, c, n-1);
}
void move(char a, char b)
{
printf("%c->%c\n", a, b);
}
Copy the code2.2) Find the depth of binary tree
The depth here refers to the maximum height of the binary tree from the root to the leaf. For example, if there is only one node, the depth is 1, and if there are N layers, the height is N.
int depth(BTNode* root)
{
if (root == NULL)
return 0;
else{ int lDepth = depth(root->left); Int rDepth = depth(root->right); // Get the right subtree depthreturnlDepth>rDepth? lDepth+1: rDepth+1; // the depth of the binary tree is +1.Copy the codeSo how do we understand depth functionally? We know that the purpose of this function is to find the depth of the binary tree, which means that if we do depth, depth(root) will return the correct depth of the binary tree at root. So in our code depth(root->left) returns the depth of the left subtree, and depth(root->right) returns the depth of the right subtree. Although we haven’t finished writing depth at this point, we believe that depth will do the job correctly. So we get lDepth and rDepth, and then by comparison return the larger value plus 1 as the depth of the binary tree.
If this is confusing, imagine that the function depth(root->left) called in depth is another function with the same name that does the same thing. In Base Case, when root==NULL, the depth is 0 and the function returns 0.
2.3) Judge whether the binary tree is balanced
A balanced binary tree is one where the depth difference between the left and right subtrees of any node is no more than 1. To determine whether a binary tree is balanced, a recursive algorithm can be used.
int isBalanceBTTop2Down(BTNode *root)
{
if(! root)return 1;
int leftHeight = btHeight(root->left);
int rightHeight = btHeight(root->right);
int hDiff = abs(leftHeight - rightHeight);
if (hDiff > 1) return 0;
return isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right);
}
Copy the codeRoot is a balanced binary tree, that is, the depth difference between the left and right subtrees of all nodes is not greater than 1. First check whether the root satisfies the condition. If not, return 0. If yes, we need to determine whether the left and right subtrees are both balanced binary trees, if they are both, return 1, otherwise 0.
2.4) Permutation algorithm
The permutation algorithm is also a good example of recursion. I remember when I first looked at the layer upon layer of code, the head was big, but now it’s really much easier to understand from a functional point of view. First look at the code:
Void permute(int a[], int k, int n) {void permute(int a[], int k, int n) {if (k == n-1) {
printIntArray(a, n); // Output array}else {
int i;
for(i = k; i < n; i++) { swapInt(a, i, k); // permute(a, k+1, n); SwapInt (a, I, k); // Restore the original sequence}}}Copy the codeThe perm(a, k, n) function outputs all permutations of array A starting at position K, with array length n. So when we call our program, we call perm(a, 0, n), which is all permutations of the output array starting at position 0, which is all permutations of the array. The base condition is k==n-1, the last element has been reached, the permutation has been completed, and the output is direct. Otherwise, each element starting at position K swaps with the value of position K (including itself), and then goes through the next permutation, remembering to restore the original sequence when it’s done.
If the array a aan na a =3, then the program calls perm(a, 0, 3) : Swap 0, 0 for the first time and execute perm(a, 1, 3). Swap 0, 0 again and the array is restored to its original value. Perm (a, 1, 3) is executed. When the array is finished, swap 1, 0 again, and the array is restored to its original value. Swap 2,0 for the third time and execute perm(a, 1, 3). Swap 2,0 and restore the array to its original value.
That is, functionally, we first determine the 0th position and then call perm(a, 1, 3) to print all permutations starting with 1. The possible value of the 0th position is a[0], a[1],a[2]. This ensures the possible value of the 0th position by swapping. Remember to restore the initial value after each swap.
If a={1,2,3}, then the output of the program is: 1 2 3, 1 3,2 1 3,2 3 1, 3 1 2. That is, the permutation of the first value in order 1 is printed, followed by the permutation of the first value in order 2 and 3.
2.5) Combination algorithm
The combinatorial algorithm can also be implemented recursively, but it is similar to the 0-1 knapsack problem. So either you pick it or you don’t pick it, and you don’t pick repeated numbers. The complete code is as follows:
Void combination(int a[], int n) {int *select = (int *)calloc(sizeof(int), n); // select an auxiliary array to store the selected number int k;for(k = 1; k <= n; k++) { combinationUtil(a, n, 0, k, select); / / void combinationUtil(int a[], int n, int I, int k, int *select) {/ / void combinationUtil(int a[], int n, int I, int k, int *select) {if (i > n) return; // If the location is outside the range of the array, it will return a segment errorif(k == 0) {// Select the selected number int j;for (j = 0; j < n; j++) {
if (select[j])
printf("%d ", a[j]);
}
printf("\n");
} else{ select[i] = 1; combinationUtil(a, n, i+1, k-1, select); Select [I] = 0; select[I] = 0; combinationUtil(a, n, i+1, k, select); Int I +1; int I +1; int I +1;Copy the code2.6) Print the string in reverse order
This is relatively simple, the code is as follows:
void reversePrint(const char *str)
{
if(! *str)return;
reversePrint(str + 1);
putchar(*str);
}
Copy the code2.7) Reverse linked list
List inversions are usually implemented iteratively, but if you want to be a bit different, you can use recursion, as shown in the asList directory of the repository.
/** * list in reverse order, recursive implementation. */ ListNode *listReverseRecursive(ListNode *head) {if(! head || ! head->next) {return head;
}
ListNode *reversedHead = listReverseRecursive(head->next);
head->next->next = head;
head->next = NULL;
return reversedHead;
}
Copy the codeThe resources
- Jinsong “Linux C programming” recursion chapter
- Data structure and algorithm -C language implementation