Some Classical Recursive Functions
Table of Contents
In this post, I will list the commonly met recursive functions that can light
the road for further investigation into the magic world of computer science.
I am not an excellent programmer myself, but through delight practice, the
little but essential part of the RECURSIVE PROBLEMS can be understood. So I will
present some examples to illustrate what I mean.
1 Find the maximum element of an array recursively.
One possible solution to this problem is as follows, the basic idea is to use
the function f_max to find the rest of the array (excluding the first element
of the array), and a max macro is used to return the first element and the rest
of the "maximum" element.
#define max(a,b) (a) > (b) ? (a) : (b) int f_max(int *a,int start,int end) { if (start == end) { return a[start]; } return max(a[start],f_max(a,start + 1,end)); } void test_max(void) { int a[] = { 12,1,22,56,4 }; printf("max=%d ",f_max(a,0,4)); }
Another way to find the maximum element is to use the binary method, which means to first split the array into two sub-arrays, and find the maximum element in each sub-array and return the bigger one of these two sub-max-maximum number.
int f_max_2(int *a,int start,int end) { if (start == end) { return a[start]; } else { return max(f_max_2(a,start,(start + end) / 2),f_max_2(a,(start + end) / 2 + 1,end)); } }
2 Recursively output the digits of a number num under base base. e.g., 7 under base 2 is "111".
void get_digits(int num,int base) { if (num / base == 0) { printf("%d",num % base); } else { get_digits(num/base,base); printf("%d",num % base); } }
3 Compute "n choose k".
It is important to get the recursive definition of c_n^k, one way to think about is "to be or not to be", the kth element can or can't be selected in a certain selecting process.
int F(int n,int k) { if (n == k) { return 1; } if (k == 0) { return 1; } return F(n - 1, k) + F(n - 1,k - 1); }
The dynamic programming method is as follows:
void print_c_n_k_table(int table[][20],int num_of_rows) { printf("table elements: "); for (int i = 0;i < num_of_rows;i++) { for (int j = 0;j <= i;j++) { printf("%d ",table[i][j]); } printf(" "); } } int dp_c_n_k(int n,int k) { int table[20][20]; for (int i = 0;i < 20;i++) { for (int j = 0;j < 20;j++) { table[i][j] = 0; if (i == j) { table[i][j] = 1; } if (j == 0) table[i][j] = 1; } } print_c_n_k_table(table,20); for (int i = 0;i < 20;i++) { for (int j = 0;j < 20;j++) { if (table[i][j] == 0) { table[i][j] = table[i - 1][j] + table[i - 1][j - 1]; } print_c_n_k_table(table,i); if ((i == n) && (j == k)) { return table[i][j]; } } printf(" "); } return 0; }