函数递归：递归是编程的一种技术，指的是函数在其内部，调用自身

举例：利用函数递归，顺序打印一个整数的每一位

void Print(int n)//打印n的每一位 { if (n > 9) { Print(n / 10);//打印除最后一位以外数字 } printf("%d ", n % 10);//打印最后一位数字 } int main() { int n = 0; scanf("%d", &n); Print(n);//就是能将n的每一位按照顺序打印到屏幕上 return 0; }

练习：求第n个斐波那契数

前两项固定：(F_0=0 , F_1=1) 从第 3 项开始，每一项 = 前两项之和

解法1：

// 求第n个斐波那契数 int Fib(int n) { if (n == 0) return 0; else if (n == 1) return 1; else /* 性能差：分叉递归，大量重复计算，时间复杂度O(2ⁿ)。 不易栈溢出：串行执行，算完一个分支、出栈释放后再算下一个。 栈最大深度只有n层，不会把所有分叉同时压栈。 */ return Fib(n - 1) + Fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int r = Fib(n); printf("%d", r); return 0; }

总结：函数递归虽好，但是也需要综合考虑下性能问题和栈溢出问题，有时候循环也可以很好代替栈溢出；递归适合结构天然嵌套、深度可控的问题，代码简洁直观；循环适合规模大、追求性能，避免重复计算与栈溢出。

解法2：

// 求第n个斐波那契数 int Fib(int n) { int a = 0; int b = 1; int c = 0; if (n < 0) return -1; else if(n == 0) return n; else if(n == 1) return n; else { while (n > 1) { c = a + b;// 第几个0 1 2 3 4 5 6 7 8 9 10 a = b; // 值 0 1 1 2 3 5 8 13 21 34 55 b = c; // a b c n--; // a b c } // a b c return b; // a b c } } int main() { int n = 0; scanf("%d", &n); int r = Fib(n); printf("%d", r); return 0; }

题目 1：递归实现整数次方（支持正负底数、正负指数）

题目描述：写递归函数my_pow，计算 \(n^k\)。支持正指数、负指数；0 的负数次方无意义，需要报错提示。

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> double my_pow(int n, int k) { if (n == 0 && k < 0) { printf("错误：0的负数次方无意义！\n"); return 0; } else if (k == 0) return 1.0; else if (k > 0) return n * my_pow(n, k - 1); else return 1.0 / my_pow(n, -k); } int main() { int n, k = 0; printf("请输入你要求的数字的次方，例如2的三次方，请输入： 2 3\n"); scanf("%d%d", &n, &k); double r = my_pow(n, k); printf("%.4lf", r); return 0; }

题目 2：递归求一个整数各位数字之和

题目描述：写递归函数DigitSum(n)，输入一个整数（可以是负数），返回组成它的数字之和。例如调用DigitSum(1729)，返回 1+7+2+9 = 19。

#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> int DigitSum(int n) { n = abs(n); if (n > 9) return n % 10 + DigitSum(n / 10); else return n; } int main() { int n = 0; scanf("%d", &n); int r = DigitSum(n); printf("%d", r); return 0; }

扫雷游戏的改造

新增：计时模块，递归展开机制，第一次不被炸死机制

这次改动只涉及 game.c文件

#define _CRT_SECURE_NO_WARNINGS 1 #include "game.h" void InitBoard(char board[ROWS][COLS], int rows, int cols, char set)// 初始化棋盘 { int i = 0; int j = 0; for (i = 0; i < rows; i++) { for (j = 0; j < cols; j++) { board[i][j] = set; } } } void DisplayBoard(char arr[ROWS][COLS], int row, int col)// 展示棋盘 { int i, j; for (i = 0; i <= col; i++) printf("%d ", i); printf("\n"); for (i = 1; i <= row; i++) { printf("%d ", i); for (j = 1; j <= col; j++) { printf("%c ", arr[i][j]); } printf("\n"); } printf("\n"); } void SetMine(char mine[ROWS][COLS], int row, int col)// 布置地雷 { int count = MINE_COUNT; while(count > 0) { int x = rand() % row + 1; int y = rand() % col + 1; if (mine[x][y] == '0') { mine[x][y] = '1'; count--; } } } int GetMineCount(char mine[ROWS][COLS], int x, int y)// 计算坐标周围地雷 { return mine[x - 1][y - 1] + mine[x - 1][y] + mine[x - 1][y + 1] + mine[x][y - 1] + mine[x][y + 1] + mine[x + 1][y - 1] + mine[x + 1][y] + mine[x + 1][y + 1] - 8 * '0';// '0' - '0' = 0; asi值 '0' 为 48； } void ShowElapsedTime(time_t start)// 计算当前用时 { time_t elapsed = time(NULL) - start; printf("当前用时%zu分，%zu秒\n", elapsed / 60, elapsed % 60); } int ExpandBoard(char mine[ROWS][COLS], char show[ROWS][COLS], int row, int col, int x, int y)// 爆炸式递归展开 { int i; int j; int count; // 计算排查次数 int num = 0; if (x < 1 || x > row || y < 1 || y > col) return 0; else if (show[x][y] != '*')// return 0; num = GetMineCount(mine, x, y); show[x][y] = (num == 0) ? ' ' :(char) ( num + '0'); count = 1; if (num == 0)//如果没有地雷 ，就向四周展开 { for (i = x - 1; i <= x + 1; i++)//三行 { for (j = y - 1; j <= y + 1; j++)//三列 count += ExpandBoard(mine, show, ROW, COL, i, j);//对应左边，再次递归判断，count变量互不影响 } } return count; } void FindMine(char mine[ROWS][COLS], char show[ROWS][COLS], int row, int col)// 排查地雷函数 { int x = 0, y = 0; int count = 0; int win = 1; int first = 1; time_t start = time(NULL); while (count < row * col - MINE_COUNT) { printf("请输入要排查坐标"); int ret = scanf("%d%d", &x, &y); // ret 接收 scanf 的返回值（成功读取的个数） if (ret != 2) // 没读到两个整数，说明输入了字母等非法内容 { int ch; // 用来存放从缓冲区取出的字符 while ((ch = getchar()) != '\n' && ch != EOF) // 逐字符清空，直到读到回车或文件结束 ; // 循环体什么都不做，目的就是"把垃圾吃掉" printf("输入有误，请重新输入两个整数坐标\n"); continue; // 跳过本次循环后面的判断，重新要求输入 } printf("\n"); if (x > 0 && x <= row && y > 0 && y <= col)// 坐标合法 { if (show[x][y] == '*') { if (first && mine[x][y] == '1')// 防止冤大头第一次就被炸死 { int nx = 0; int ny = 0; do { nx = rand() % ROW + 1; ny = rand() % COL + 1; } while (mine[nx][ny] == '1'); mine[nx][ny] = '1'; mine[x][y] = '0'; } if (mine[x][y] == '0')// 不是雷 { // 计算周围雷的个数 int num = GetMineCount(mine, x, y); count += ExpandBoard(mine, show, ROW, COL, x, y); DisplayBoard(show, row, col); first = 0;// 第一次排雷已结束 ShowElapsedTime(start); } else// 这个位置是雷 { printf("很遗憾，你被炸死了\n"); DisplayBoard(mine, row, col); win = 0; ShowElapsedTime(start); break; } } else { printf("该坐标已经排查过了\n"); } } else printf("输入坐标非法\n"); } if (win == 1) { printf("恭喜你排雷成功\n"); DisplayBoard(mine, ROW, COL); } }

祝大家天天开心