C语言-实验13-递归算法
本系列将以一个学习者的眼光，从零基础一步一步学会最基础的C语言编程，本文将讲解C语言第十三个板块：递归算法。
递归算法是编程中非常经典且重要的算法思想，它的核心是函数自己调用自己，把一个复杂的大问题，拆解成和原问题结构相同、规模更小的子问题，直到拆解成最简单的边界问题，再逐步回溯得到结果。
递归和我们上一节学的递推是一对“兄弟算法”，递推是自底向上，递归是自顶向下，理解递归能帮你大幅简化复杂问题的代码逻辑。
递归算法
1. 基本定义
递归：函数直接或间接调用自身，将原问题分解为规模更小的同类子问题，通过解决子问题最终解决原问题。
2. 递归三要素
-
边界条件
递归必须有停止的条件，否则会无限调用导致程序崩溃，是递归的“终止开关”。
-
递归公式
原问题与子问题之间的关系，告诉程序如何把大问题拆成小问题。
-
递归调用
函数自身调用，逐步缩小问题规模。
3. 递归执行过程
分为两个阶段：
-
递推阶段：从原问题出发，不断调用自身，缩小问题规模，直到到达递归出口；
-
回溯阶段：从递归出口开始，反向计算，逐步返回结果，最终得到原问题答案。
4. 递归 vs 递推
| 特性 | 递归 | 递推 |
|---|---|---|
| 执行方式 | 函数自调用，自顶向下 | 循环迭代，自底向上 |
| 代码逻辑 | 简洁直观，符合人类思维 | 代码稍繁琐，需要手动找规律 |
| 内存占用 | 较高（函数栈帧累积） | 较低（仅循环变量） |
| 效率 | 较低（函数调用开销） | 较高（无额外开销） |
| 适用场景 | 树形结构、分治问题、难以找递推公式的问题 | 数列计算、简单规律推导 |
示例
1.求阶乘
求n的阶乘，公式：n! = n × (n-1)!，边界条件：0! = 1，1! = 1
递归思路：边界：n==0 || n==1，返回1；递归公式：factorial(n) = n * factorial(n-1)。
#include <stdio.h>
int factorial(int n) { if (n == 0 || n == 1) { return 1; } return n * factorial(n - 1);}
int main() { int n; printf("请输入一个整数："); scanf("%d", &n); printf("%d的阶乘 = %d\n", n, factorial(n)); return 0;}2.斐波那契数列
斐波那契数列：F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)（n≥3）
递归思路：边界：n==1 || n==2，返回1；递归公式：fib(n) = fib(n-1) + fib(n-2)。
#include <stdio.h>
int fib(int n) { if (n == 1 || n == 2) { return 1; } return fib(n - 1) + fib(n - 2);}
int main() { int n; scanf("%d", &n); printf("斐波那契第%d项 = %d\n", n, fib(n)); return 0;}3.蟠桃记
孙悟空每天吃桃子总数的一半多1个，第n天只剩1个桃子，求第一天有多少个桃子。
递归思路：边界：第n天，桃子数=1；递归公式：前一天数量 = (当天数量 + 1) × 2。
#include <stdio.h>
long long peach(int day, int n) { if (day == n) { return 1; } return (peach(day + 1, n) + 1) * 2;}
int main() { int n; scanf("%d", &n); printf("第一天桃子数：%lld\n", peach(1, n)); return 0;}4.递归求数组元素和
问题：用递归计算一个数组所有元素的和。
递归思路：边界：数组下标越界（无元素），和为0；递归公式：总和 = 当前元素 + 剩余元素的和。
#include <stdio.h>
int sumArr(int arr[], int index, int len) { if (index >= len) { return 0; } return arr[index] + sumArr(arr, index + 1, len);}
int main() { int arr[] = {1, 2, 3, 4, 5}; int len = sizeof(arr) / sizeof(arr[0]); printf("数组和 = %d\n", sumArr(arr, 0, len)); return 0;}应用
6-1 sdut-C语言实验-快速排序
本题要求实现一个快速排序函数。
给定 N ( N<= 100000 ) 个 int 范围内的整数，要求用快速排序对数据进行升序排列。
函数接口定义：
其中 array[] 、 l 、r 都是用户传入的参数。 array[] 是需要排序的数组，数组长度不会超过100000； l 和 r 是需要进行排序的左端点和右端点。
裁判测试程序样例：
输入示例：
输出示例：
6-1 解答：
void Quick_sort(int array[],int l,int r){ if(l>=r){ return 0; } int pivot=array[l]; int i=l,j=r; while(i<j){ while(i<j&&array[j]>=pivot) j--; array[i]=array[j]; while(i<j&&array[i]<=pivot) i++; array[j]=array[i]; } array[i]=pivot; Quick_sort(array,l,i-1); Quick_sort(array,i+1,r);}6-2 sdut-C语言实验-二分查找
本题要求实现一个二分查找函数。
给出含有 n 个数的升序序列，保证序列中的数两两不相等，这n个数编号从1 到n。
然后给出 q 次询问，每次询问给出一个数x，若x存在于此序列中，则输出其编号，否则输出-1。
函数接口定义：
其中 array 、 l 、 r 、 x都是用户传入的参数。 array 是要进行查询的序列，保证序列有序且出现的数字均不重复； l 和 r 是二分查找的区间的左端点和右端点；x 代表要在序列中查询的值。
当在序列中查询到 x 时，函数返回 x 在序列中出现的位置编号；否则函数返回 -1。
裁判测试程序样例：
输入示例：
输出示例：
6-2 解答：
int Binary_search(int array[],int l,int r,int x){ while(l<=r){ int mid=(l+r)/ 2; if(array[mid]==x){ return mid; } else if(array[mid]<x){ l=mid+1; }else{ r=mid-1; } } return -1;}7-1 sdut-C语言实验-母牛的故事
计算组合数。C(n,m),表示从n个数中选择m个的组合数。
计算公式如下：
若：m=0，C(n,m)=1
否则， 若 n=1，C(n,m)=1
否则，若m=n，C(n,m)=1
否则 C(n,m) = C(n-1,m-1) + C(n-1,m)
输入格式：第一行是正整数N (1 <= N<= 100)，表示有N组要求的组合数。
接下来N行，每行两个整数n，m (0 <= m <= n <= 20)。
输出格式：输出N行。每行输出一个整数表示C(n,m)。
输入示例：
输出示例：
7-1 解答：
#include <stdio.h>
int fun(int n,int m);
int main(){ int t,n,m,i; scanf("%d",&t); for(i=1;i<=t;i++){ scanf("%d %d",&n,&m); printf("%d\n",fun(n,m)); } return 0;}
int fun(int n,int m){ if(m==0){ return 1; }else if(n==1){ return 1; }else if(m==n){ return 1; }else{ return fun(n - 1, m - 1) + fun(n - 1, m); }}7-2 sdut-C语言实验-汉诺塔
汉诺塔（又称河内塔）问题是印度的一个古老的传说。
开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒A、B和C，A上面套着n个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从A棒搬到C棒上，规定可利用中间的一根B棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。
僧侣们搬得汗流满面，可惜当n很大时这辈子恐怕就很搬完了。
聪明的你还有计算机帮你完成，你能写一个程序帮助僧侣们完成这辈子的夙愿吗？
输入格式：输入金片的个数n (1 <= n <= 10)。
输出格式：输出搬动金片的全过程。格式见样例。
输入示例：
输出示例：
7-2 解答：
#include <stdio.h>
void hanni(int n,char from,char temp,char to);
int main(){ int n; scanf("%d",&n); hanni(n,'A','B','C'); return 0;}
void hanni(int n,char from,char temp,char to){ if(n==1){ printf("Move disk %d from %c to %c\n", n, from, to); return 0; } hanni(n-1,from,to,temp); printf("Move disk %d from %c to %c\n", n, from, to); hanni(n-1,temp,from,to);}7-3 sdut-C语言实验-简单递归函数
递归函数其实是一种特使的嵌套调用函数，特殊的地方是函数调用了自己，而且可以多层调用。
下面的函数就是一个简单的递归函数调用。
F(m, n)的定义是：
若m=0，返回n+1。
若m>0且n=0，返回F(m-1,1)。
若m>0且n>0，返回F(m-1,F(m,n-1))。
给出 m 和 n，计算 F(m, n) 的值。
输入格式：第一行输入一个整数 t， 代表有 t 组数据。(1 <= t <= 15)
每组数据输入一行，包含两个非负整数 m，n。(0 <= m <= 3, 0 <= n <= 10)
输出格式：每组数据输出一行，为 F(m, n) 的答案。
输入示例：
输出示例：
7-3 解答：
#include <stdio.h>
int F(int m,int n);
int main(){ int a; int m,n,sum; scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%d %d",&m,&n); sum=F(m,n); printf("%d\n",sum); } return 0;}
int F(int m,int n){ if(m==0){ return n+1; }else if(m>0&&n==0){ return F(m-1,1); }else if(m>0&&n>0){ return F(m-1,F(m,n-1)); }}7-4 sdut-C语言实验-青蛙过河
一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，石柱L面积只容得下一只青蛙落脚，同样右岸也有一石柱R，石柱R面积也只容得下一只青蛙落脚。有一队青蛙从小到大编号：1，2，…，n。
初始时，青蛙只能趴在左岸的石头 L 上，按编号一个落一个，小的落在大的上面-----不允许大的在小的上面。
在小溪中有S个石柱、有y片荷叶。溪中的每个石柱上如果有多只青蛙也是大在下、小在上，每个荷叶只允许一只青蛙落脚。
对于右岸的石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下。
当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪中荷叶、溪中石柱跳至右岸R上的青蛙也不允许再离开。
那么在已知小溪中有 s 根石柱和 y 片荷叶的情况下，最多能跳过多少只青蛙？
输入格式：第一行输入一个整数 t， 代表有 t 组数据。(1 <= t <= 15)
每组占一行，每行包含2个数s(s是小溪中的石柱数目)、y(y是小溪中的荷叶数目)。（0 <= s <= 10 , 0 <= y <= 10)
输出格式：对每组输入，输出有一行，输出最多能跳过的青蛙数目。
输入示例：
输出示例：
7-4 解答：
#include <stdio.h>
int jump(int s,int y);
int main(){ int t; scanf("%d",&t); while(t--){ int s,y; scanf("%d %d",&s,&y); printf("%d\n",jump(s,y)); } return 0;}
int jump(int s,int y){ if(s==0){ return y+1; } return 2*jump(s-1,y);}7-5 sdut-C语言实验-第k小的数
现有一个包含n个整数（1<=n<=900000）的无序序列(保证序列内元素各不相同)，输入一个整数k（1<=k<=n）,请用较快的方式找出该序列的第k小数并输出。
输入格式：第一行先输入两个整数，n和k。
接下来是一行输入n个由空格分开的互不相同的整数num(1<=num<=90000000)。
输出格式：输出该组数据中第k小的数num。
输入示例：
输出示例：
7-5 解答：
#include <stdio.h>#include <stdlib.h>
int cmp(const void *a,const void *b){ return *(int*)a-*(int*)b;}
int main(){ int n,k; scanf("%d %d",&n,&k); int arr[900000]; for(int i=0;i<n;i++) { scanf("%d",&arr[i]); } qsort(arr,n,sizeof(int),cmp); printf("%d\n",arr[k-1]); return 0;}l7-6 sdut-C语言实验-第X大的数
X最近爱上了区间查询问题，给出N (N <= 100000) 个数，然后进行M (M <= 50) 次询问，每次询问时，输入一个数X (1 <= X <= N)，输出N个数中第X大的数。
输入格式：首先输入一个整数N，代表有N个数，下面一行包含N个整数，用空格隔开。然后为一个整数M，代表有M次询问，下面的M行，每行一个整数X。
输出格式：输出N个数中第X大的数。
输入示例：
输出示例：
7-6 解答：
#include <stdio.h>#include <stdlib.h>
int cmp(const void *a,const void *b){ return *(int*)b-*(int*)a;}
int main(){ int n; scanf("%d",&n); int arr[100000]; for(int i=0;i<n;i++) { scanf("%d",&arr[i]); } qsort(arr,n,sizeof(int),cmp); int m; scanf("%d",&m); for(int i=0;i<m;i++){ int j; scanf("%d",&j); printf("%d\n",arr[j-1]); } return 0;}7-7 sdut-C语言实验-神奇的函数
神奇的函数是这样被定义的：
输入格式：第一行是正整数N (1 <= N<= 30)，表示有N组数据。
接下来N行，每行两个整数n，m (1 <= n, m <= 10)。
输出格式：输出N行。每行输出一个整数表示F(n,m)。
输入示例：
输出示例：
7-7 解答：
#include <stdio.h>
int F(int n,int m);
int main(){ int x,n,m; scanf("%d",&x); for(int i=0;i<x;i++){ int sum; scanf("%d %d",&n,&m); sum = F(n,m); printf("%d\n",sum); } return 0;}
int F(int n,int m){ if(n==1||m==1){ return 1; }else{ return F(n-1,m)+F(n,m-1); }}总结
OK了，今天你学会了C语言程序的递归算法及其相关知识点！那么我们一起加油吧！
支持与分享
如果这篇文章对你有帮助，欢迎分享给更多人或赞助支持！
评论区
音乐
暂未播放