C语言函数递归调用的8个示例

C语言函数递归调用的8个示例递归两要素终止条件基线递归条件缩小问题规模例1阶乘 n!#includestdio.hlongfact(intn){if(n0||n1)return1;// 终止条件returnn*fact(n-1);// 递归n! n × (n-1)!}intmain(){printf(5! %ld\n,fact(5));// 120return0;}fact(4) └─ 4 × fact(3) 4 × 6 24 └─ 3 × fact(2) 3 × 2 6 └─ 2 × fact(1) 2 × 1 2 └─ return 1例2斐波那契数列// F(1)1, F(2)1, F(n)F(n-1)F(n-2)intfib(intn){if(n1||n2)return1;// 终止条件returnfib(n-1)fib(n-2);// 递归}intmain(){for(inti1;i10;i)printf(%d ,fib(i));// 1 1 2 3 5 8 13 21 34 55return0;}⚠️ 树形递归时间复杂度 O(2ⁿ)。可用迭代优化。例3汉诺塔// n个盘子A→CB为辅助voidhanoi(intn,charA,charB,charC){if(n1){printf(盘%d: %c → %c\n,n,A,C);// 终止1个盘子直接移return;}hanoi(n-1,A,C,B);// n-1个A→Bprintf(盘%d: %c → %c\n,n,A,C);// 第n个A→Chanoi(n-1,B,A,C);// n-1个B→C}intmain(){hanoi(3,A,B,C);// 最少步数 2³ - 1 7return0;}输出盘1: A → C 盘2: A → B 盘1: C → B 盘3: A → C 盘1: B → A 盘2: B → C 盘1: A → C例4求最大公约数辗转相除// gcd(a,b) gcd(b, a%b)直到 b0intgcd(inta,intb){if(b0)returna;// 终止条件returngcd(b,a%b);// 递归辗转相除}intmain(){printf(gcd(56, 98) %d\n,gcd(56,98));// 14printf(gcd(17, 31) %d\n,gcd(17,31));// 1互质return0;}gcd(56, 98) └─ gcd(98, 56) gcd(56, 42) gcd(42, 14) gcd(14, 0) 14例5求 x 的 n 次方快速幂// x^n x^(n/2) × x^(n/2) (n为偶)// x^n x × x^(n-1) (n为奇)doublepower(doublex,intn){if(n0)return1.0;// 终止x⁰1if(n0)return1.0/power(x,-n);// 处理负指数if(n%20){// n为偶数doublehalfpower(x,n/2);returnhalf*half;// xⁿ (x^(ⁿ/²))²}returnx*power(x,n-1);// n为奇数}intmain(){printf(2^10 %.0f\n,power(2,10));// 1024printf(3^-2 %.4f\n,power(3,-2));// 0.1111return0;}时间复杂度 O(log n)比循环乘 n 次O(n)快得多。例6数组求和// 求 arr[0..n-1] 的和intsum(intarr[],intn){if(n0)return0;// 终止空数组returnarr[n-1]sum(arr,n-1);// 最后一个 前面n-1个的和}intmain(){inta[]{1,2,3,4,5};printf(sum %d\n,sum(a,5));// 15return0;}sum(arr, 5) 5 sum(arr, 4) └─ 4 sum(arr, 3) └─ 3 sum(arr, 2) └─ 2 sum(arr, 1) └─ 1 sum(arr, 0) 1 0 1例7反转字符串#includestring.h// 原地反转 s[left..right]voidreverse(chars[],intleft,intright){if(leftright)return;// 终止相遇或越过charts[left];s[left]s[right];s[right]t;reverse(s,left1,right-1);// 递归处理内部}intmain(){charstr[]hello;reverse(str,0,strlen(str)-1);printf(%s\n,str);// ollehreturn0;}reverse(hello, 0, 4) 交换 s[0]↔s[4]: oellh └─ reverse(oellh, 1, 3) 交换 s[1]↔s[3]: olleh └─ reverse(olleh, 2, 2) → 终止例8二分查找// 在有序数组 a[left..right] 中查找 target返回下标-1 表示未找到intbinary_search(inta[],intleft,intright,inttarget){if(leftright)return-1;// 终止未找到intmidleft(right-left)/2;if(a[mid]target)returnmid;// 终止找到了if(a[mid]target)returnbinary_search(a,left,mid-1,target);// 左半区elsereturnbinary_search(a,mid1,right,target);// 右半区}intmain(){inta[]{1,3,5,7,9,11,13};printf(7 的下标: %d\n,binary_search(a,0,6,7));// 3printf(8 的下标: %d\n,binary_search(a,0,6,8));// -1return0;}找 7: a[0..6], mid3, a[3]7 → 找到 ✓ 找 8: a[0..6], mid3, a[3]78 → 查[4..6] └─ mid5, a[5]118 → 查[4..4] └─ mid4, a[4]98 → 查[4..3] → 未找到 ✗递归设计 Checklist步骤检查项①终止条件写对了吗n0、leftright、等等②每次递归问题规模在缩小吗n→n-1、左/右区间缩小③递归返回值正确拼接了吗n * fact(n-1)、fib(n-1)fib(n-2)④会不会栈溢出深度太大考虑迭代递归 vs 迭代递归迭代代码简洁优美可能冗长效率函数调用开销大高效栈深层递归可能栈溢出无此问题适用树/图、分治、数学归纳线性递推