二、函数的递归
0x00 递归的定义
📚 程序调用自身称为递归（recursion）
1. 递归策略只需要少量的程序就可以描述解题过程所需要的多次重复计算，大大减少代码量；
2. 递归的主要思考方式在于：把大事化小；
📌 注意事项：
1. 存在跳出条件，每次递归都要逼近跳出条件；
2. 递归层次不能太深，避免堆栈溢出；
💬 递归演示
“接收一个整型值，按照顺序打印它的每一位（eg. 输入1234，输出 1 2 3 4）”
void space(int n) { if (n > 9) { space(n / 10); } printf("%d ", n % 10); } int main() { int num = 1234; space(num); return 0; }
🚩 >>> 1 2 3 4
🔑 解析：
0x01 堆栈溢出
📚 堆栈溢出现象 - stackoverflow
1. 水满则溢，堆栈也有容量限制，当其超出限制，就会发生溢出；
2. 堆栈溢出可以理解为“吃多了吐”，队列溢出就是“吃多了拉”；
3. 程序员的知乎：Stack Overflow - Where Developers Learn, Share, & Build Careers
💀 危害：
1. 堆栈溢出时会访问不存在的RAM空间，造成代码跑飞，此时无法获取溢出时上下文数据，也无法对后续的程序修改提供有用信息；
2. 造成安全威胁，常见的攻击类型有：修改函数的返回地址，使其指向攻击代码，当函数调用结束时程序跳转到攻击者设定的地址，修改函数指针，长跳转缓冲区来找到可溢出的缓冲区；
💬 堆栈溢出现象演示；
void test(int n) { if(n < 10000) { test(n + 1); } } int main() { test(1); return 0; }
0x02 递归的用法
💬 手写strlen函数
1. “创建临时变量count方法”
int my_strlen(char* str) { int count = 0; while (*str != '\0') { count++; str++; } return count; } int main() { char arr[] = "abc"; int len = my_strlen(arr); // 传过去的是首元素地址； printf("len = %d\n", len); return 0; }
🚩 >>> len = 3
2. “不创建临时变量，利用递归完成”
/* my_strlen("abc"); 1 + my_strlen("bc"); 1 + 1 + my_strlen("c"); 1 +1 + 1 + my_strlen(""); 1 + 1 + 1 + 0 3 */ int rec_strlen(char* str) { if (*str != '\0') return 1 + rec_strlen(str+1); else return 0; } int main() { char arr[] = "abc"; int len = rec_strlen(arr); printf("len = %d\n", len); return 0; }
🚩 >>> len = 3
0x03 递归与迭代
❓ 何为迭代：
“重复执行程序中的循环，直到满足某条件时才停止，亦称为迭代”
📚 迭代法：也称辗转法，是一种不断用变量的旧值递推新值的过程；
💬 求n的阶乘（不考虑溢出）；
“阶乘公式： n! = n(n-1)”
int Fac(int n) { if (n <= 1) return 1; else return Fac(n-1) * n; } int main() { int n = 0; scanf("%d", &n); int ret = Fac(n); printf("%d\n", ret); return 0; }
💬 求第n个斐波那契数（不考虑溢出）；
“斐波拉契数列：0，1，1，2，3，5，8，13，21，34，55...”
int Fib(int n) { if (n <= 2) return 1; else return Fib(n-1) + Fib(n-2); } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("第%d个斐波拉契数为%d\n", n, ret); return 0; }
🚩 >>> （假设输入10） 第10个斐波那契数为55
>>> （假设输入20）第20个斐波那契数为6765
>>> （假设输入50）...（程序运行中，似乎卡住了）
0x04 非递归
❓ 我们发现了问题，如果用Fib这个函数计算第50个斐波那契数字的时候需耗费很长的时间；
使用Fic函数求10000的阶乘（不考虑结果的正确性），程序会崩溃；
🔑 耗费很长时间的原因是 Fib函数在调用的过程中很多计算其实在一直重复，比如计算第50个斐波那契数就要计算第49个，计算第49个斐波那契数就要计算第48个……以此类推；
💡 优化方法：将递归改写为非递归；
📜 箴言：
1. 许多问题是以递归的形式进行解释的，这只是因为他比非递归的形式更为清晰；
2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些；
3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿运行时开销；
💬 使用非递归的方式写；
1 1 2 3 5 8 13 21 34 55...
a b c
int Fib(int n) { int a = 1; int b = 1; int c = 1; while (n > 2) { c = a + b; a = b; b = c; n--; } return c; } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }
💬 非递归方式求阶乘
int fac(int n) { int ret = 1; while(n > 1) { ret *= n; n -= 1; } return ret; } int main() { int n = 0; scanf("%d", &n); int ret = fac(n); printf("%d\n", ret); return 0; }
三、练习
0x00 练习1
1. 写一个函数可以判断一个数是不是素数；
2. 写一个函数判断一年是不是闰年；
3. 写一个函数，实现一个整形有序数组的二分查找；
4. 写一个函数，每调用一次这个函数，就会将num的值增加1；
💬 写一个is_prime()函数可以判断一个数是不是素数；
“质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。”
#include <stdio.h> int is_prime(int n) { int i = 0; for(i=2; i<n; i++) { if(n % i == 0) return 0; } if(i == n) return 1; else return 0; } int main() { int n = 0; scanf("%d", &n); int ret = is_prime(n); if(ret == 1) { printf("%d是素数\n", n); } else { printf("%d不是素数\n", n); } return 0; }
💬 写一个 is_leap_year 函数判断一年是不是闰年；
int is_leap_year(int y) { if((y % 4 == 0) && (y % 100 != 0) || (y % 400 == 0)) return 1; else return 0; } int main() { int year = 0; printf("请输入年份: "); scanf("%d", &year); if(is_leap_year(year) == 1) printf("%d年是闰年\n", year); else printf("不是闰年\n"); return 0; }
💬 写一个函数，实现一个整形有序数组的二分查找；
“ int arr[] = {1,2,3,4,5,6,7,8,9,10}; ” int binary_search(int arr[], int k, int sz) { int left = 0; int right = sz - 1; while(left <= right) { int mid = (left + right) / 2; if(arr[mid] < k) left = mid + 1; else if(arr[mid] > k) right = mid - 1; else return mid; } return -1; } int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; int sz = sizeof(arr) / sizeof(arr[0]); int k = 0; printf("请输入要查找的值: "); scanf("%d", &k); int ret = binary_search(arr, k, sz); if(ret == -1) printf("找不到\n"); else printf("找到了，下标为%d\n", ret); return 0; }
💬 写一个函数，每调用一次这个函数，就会将num的值增加1；
void Add(int* pnum) { (*pnum)++; } int main() { int num = 0; Add(&num); printf("%d\n", num); Add(&num); printf("%d\n", num); Add(&num); printf("%d\n", num); return 0; }
🚩 >>> 1 2 3
0x01练习2
1. 实现一个函数，判断一个数是不是素数，利用上面实现的函数打印100到200之间的素数；
2. 交换两个整数，实现一个函数来交换两个整数的内容；
3. 自定义乘法口诀表，实现一个函数，打印乘法口诀表，口诀表的行数和列数自己指定；
💬 实现一个函数，判断一个数是不是素数；
“利用上面实现的函数打印100到200之间的素数，打印出一共有多少个素数”
int is_prime(int n) { int j = 0; for(j=2; j<n; j++) { if(n % j == 0) return 0; } return 1; } int main() { int i = 0; int count = 0; for(i=100; i<=200; i++) { if(is_prime(i) == 1) { count++; printf("%d ", i); } } printf("\n一共有%d个素数", count); return 0; }
🚩 >>> 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 一共有21个素数
💬 交换两个整数；
“实现一个函数来交换两个整数的内容”
void Swap(int* pa, int* pb) { int tmp = 0; tmp = *pa; *pa = *pb; *pb = tmp; } int main() { int a = 10; int b = 20; printf("交换前: a=%d, b=%d\n", a, b); Swap(&a, &b); printf("交换后: a=%d, b=%d\n", a, b); return 0; }
🚩 >>> 交换前: a=10, b=20 交换后: a=20, b=10
自定义乘法口诀表；
“实现一个函数，打印乘法口诀表，口诀表的行数和列数自己指定”
(eg.输入9，输出9*9口诀表，输出12，输出12*12的乘法口诀表。)
void formula_table(int line) { int i = 0; for(i=1; i<=line; i++) { int j = 0; for(j=1; j<=i; j++) { printf("%dx%d=%-2d ", j, i, i*j); } printf("\n"); } } int main() { int line = 0; printf("请定义行数: > "); scanf("%d", &line); formula_table(line); return 0; }
0x02 练习3
1. 字符串逆序，非递归方式的实现和递归方式的实现；
2. 写一个函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和；
3. 编写一个函数实现n的k次方，使用递归实现；
💬 字符串逆序
编写一个函数 reverse_string(char * string)；
将参数字符串中的字符反向排列，不是逆序打印；
要求：不能使用C函数库中的字符串操作函数；
（eg. char arr[] = "abcdef"; 逆序之后数组的内容变成：fedcba）
非递归实现：
int my_strlen(char* str) { if(*str != '\0') { return 1 + my_strlen(str + 1); } return 0; } void reverse_string(char* str) { int len = my_strlen(str); int left = 0; int right = len - 1; while(left < right) { char tmp = str[left]; str[left] = str[right]; str[right] = tmp; left++; right--; } } int main() { char arr[] = "abcdef"; reverse_string(arr); printf("%s\n", arr); return 0; }
🚩 >>> fedcba
递归实现：
1. [] 写法
int my_strlen(char* str) { int count = 0; while(*str != '\0') { count++; str++; } return count; } void reverse_string(char *str) { int len = my_strlen(str); int left = 0; // 最左下标 int right = len - 1; // 最右下标 char tmp = str[left]; str[left] = str[right]; str[right] = '\0'; // 判断条件 if(my_strlen(str + 1) >= 2) { reverse_string(str + 1); } str[right] = tmp; } int main() { char arr[] = "abcdef"; reverse_string(arr); printf("%s\n", arr); return 0; }
2. *写法
int my_strlen(char* str) { if(*str != '\0') { return 1 + my_strlen(str + 1); } return 0; } void reverse_string(char* str) { int len = my_strlen(str); char tmp = *str; *str = *(str + len-1); *(str + len-1) = '\0'; if(my_strlen(str + 1) >= 2) { reverse_string(str + 1); } *(str + len-1) = tmp; } int main() { char arr[] = "abcdef"; reverse_string(arr); printf("%s\n", arr); return 0; }
💬 写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和；
“调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19”（eg. 输入：1729，输出：19）
int digit_sum(int n) { if (n > 9) { return digit_sum(n / 10) + (n % 10); } else { return 1; } } int main() { int n = 1729; int ret = digit_sum(n); printf("%d\n", ret); return 0; }
🚩 >>> 19
🔑 解析：
digit_sum(1729)
digit_sum(172) + 9
digit_sum(17) + 2 + 9
digit_sum(1) + 7 + 2 + 9
1+7+2+9 = 19
💬 编写一个函数实现n的k次方，使用递归实现
“递归实现n的k次方”
double Pow(int n, int k) { if (k == 0) return 1.0; else if(k > 0) return n * Pow(n, k-1); else // k < 0 return 1.0 / (Pow(n, -k)); } int main() { int n = 0; int k = 0; scanf("%d^%d", &n, &k); double ret = Pow(n, k); printf("= %lf\n", ret); return 0; }
🚩 >>> （假设输入 2^3）8.000000 （假设输入 2^-3）0.125000
🔑 解析：
1. k=0，结果为1；
2. k>0，因为n的k次方等同于n乘以n的k次方-1，可以通过这个“大事化小”；
3. k<0，k为负指数幂时可化为 1 / n^k
