【C语言】函数递归编程题

目录

题目一：

题目二：

题目三：

题目四：

总结

题目一：

题目：接受一个整型值（无符号），按照顺序打印它的每一位。（递归完成）

列如：

输入：1234，输出1 2 3 4

题目解析：

  • 接受一个整型值（无符号），那就是输入的数不能为负数
  • 持续获得整数的个位值，方法为：n % 10得到个位，n / 10 得到除了个位以外的数
  • 重复n%10，n/10，n%10.....直到n%10 = n，就把一个整数拆分了
  • 需要按照顺序打印，这里使用递归是比较合适的
  • 我们使用大事化小的方式思考，当n<=9的时候，表示这个整数只剩下/只有个位，那就说明该整数为n本身
  • 当n>9的时候，可以将整数1234拆分为，123和4，因为4是很容易得到的，对1234%10=4，那我们让123先打印在屏幕上，然后再打印4
  • 以此类推，123拆分为12和3，12拆分为1和2，当想再拆分1时，发现1<=9，则只剩个位，然后将1本身进行打印，再往前进行打印
  • 下面是图解：

代码实现：

//接受一个整型值（无符号），按照顺序打印它的每一位。
//例如：输入：1234，输出 1 2 3 4.
void Print(unsigned int n)
{//n>9表示n不止1位数if (n > 9)// n/10 --> 得到除个位的其它数Print(n / 10);//当n<=9时，说明此时n只有一位数，进行n%10=nprintf("%d ", n % 10);
}
int main()
{//unsigned int 表示无符号整型unsigned int num = 0;scanf("%u", &num); //%u为无符号整形的格式化字符Print(num); //用于按照顺序打印每一位数return 0;
}

对代码进行图解：

题目二：

题目：编写函数不允许创建临时变量，求字符串的长度。（递归/迭代）

题解：

  • 求字符串的长度，在C语言中有一个库函数strlen，题目要求编写函数，那就是说让我们模拟实现strlen库函数了，我们先从简单方式开始，用迭代的方式模拟实现strlen，并且允许创建临时变量：
//使用临时变量，迭代方式模拟实现strlen
#include <string.h>
int Strlen(char* parr)
{int count = 0;while (*parr != '\0'){count++;parr++;}return count;
}
int main()
{char arr[10] = "abcdef";int n = Strlen(arr);printf("%d\n", n);return 0;
}
  • 按照这个思路，我们想想如何不使用临时变量，迭代方式模拟实现strlen呢？其实可以利用指针的计算特性 ，创建一个指向parr的指针，该指针不算临时变量，然后让该指针进行遍历，直到指向'\0'，然后利用指针计算特性：尾地址 - 首地址 = 元素个数。（因为地字符串地址中的每个字符地址是连续的）
//不使用临时变量，迭代方式模拟实现strlen
#include <string.h>
int Strlen(char* parr)
{char* tmp = parr;while (*tmp != '\0'){tmp++;}return tmp - parr;
}
int main()
{char arr[10] = "abcdef";int n = Strlen(arr);printf("%d\n", n);return 0;
}
  • 利用递归模拟实现strlen就得转变一下思路了，使用大事化小思想，当是空字符时，字符个数为0，当*parr!='\0'则最少有一个字符时，字符个数>0，那我们可以把字符串看成一个整体，进行拆分，一个字符+ (n-1)个字符，一直拆，一个字符 + (n-2)个字符.....，直到变为空字符，再从0开始往回相加，具体看代码：
//不使用临时变量，递归方式模拟实现strlen
#include <string.h>
int Strlen(char* parr)
{while (*parr != '\0'){//!='\0'时最少1个字符return 1 + Strlen(parr + 1); //parr+1 表示拿到下一个字符的地址}return 0; //当为空字符时
}
int main()
{char arr[10] = "abcdef";int n = Strlen(arr);printf("%d\n", n);return 0;
}

注意：

  • 不要写出parr++，因为这是后置++，是先将地址传过去了，才进行+1操作，这就不符合存在限制条件，当满足这个限制条件的时候，递归便不再继续这个条件了。
  • 每递归一次，都会创建一个临时指针变量str，因此parr++操作，先把原本的地址传递过去了，然后自己在+1，指向下一个字符，但并没有影响到其它的parr，parr+1也只存在于调用前那块parr空间，因此程序陷入死循环，直到栈溢出。
  • 因此，在递归时，尽量不要写前置++与后置++，因为会把parr指针的指向改变。修改本身，建议parr+ 1，这种不会修改本身，只是得到当前指向的下一个地址。

代码图解：

题目三：

题目：求n的阶乘。（不考虑溢出）

题解：

  • 用递归求n的阶乘，当n为<2时，阶乘为1，当n>=2时，可以看出n * (n-1)个阶乘，因为一个阶乘往往是从1乘到n，因此可以进行拆分，直到n<2，拆分不了了，开始返回相乘。（从后往前乘）
  • 因此得出公式：

  • 代码如下：
//递归求n的阶乘
int factorial(int n)
{if (n>=2){return n * factorial(n-1);}return 1;
}
int main()
{int n = 0;scanf("%d", &n);int sum = factorial(n);printf("%d\n", sum);return 0;
}

当然，使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。因为栈区的空间是有上限的，超过了就会导致栈溢出。对于这种情况，最好的解决办法就是将递归改写成非递归：

//迭代求n的阶乘
int factorial(int n)
{int res = 1;for (int i = 1; i <= n; i++){res *= i;}return res;
}
int main()
{int n = 0;scanf("%d", &n);int sum = factorial(n);printf("%d\n", sum);return 0;
}

当然了，结果肯定是不对的，这里解决的只是防止栈溢出的情况，要想结果正确，需要分配内存更大的类型，因为res 为整型，当数值太大，整型存储不下，就会溢出。

题目四：

题目：求第n个斐波那契数。（不考虑溢出）

题解：

  • 斐波那契数为：前两个数相加 = 当前数
  • 要使用递归进行求解，那么需要考虑限定条件，当求n<3时，斐波那契数均为1，因为想形成斐波那契数，最少需要3个数。
  • 然后我们思考n>2的情况，（第n-1个斐波那契数）+（第n-2个斐波那契数），递归，直到n<3，返回1
  • 代码如下：
//求第n个斐波那契数(递归实现)
int fibonacci(int n)
{if (n>2){return fibonacci(n - 1) + fibonacci(n - 2);}return 1;
}
int main()
{int n = 0;scanf("%d", &n);int fibonacci_number = fibonacci(n);printf("%d\n", fibonacci_number);return 0;
}

代码图解：

但是我们发现有问题：在使用这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。为什么呢？我们可以记一下数：

int count = 0;//全局变量
int fibonacci(int n)
{//统计整个递归下来，求第3个斐波那契数会执行多少次if (n == 3){count++;}if (n>2)return fibonacci(n - 1) + fibonacci(n - 2);return 1;
}
int main()
{int n = 0;scanf("%d", &n);int fibonacci_number = fibonacci(n);printf("%d\n", fibonacci_number);return 0;
}

当计算第40个斐波那契数时，n == 3的执行次数已经很大了，我们看看下面这张图：

我们发现会有很多重复的次数被重复计算，因为我们是从后往前计算的，看公式：Fb(n-1) + Fb(n-2) 这种计算方式会有很多重复的计算，比如算第10个斐波那契数：

有很多重复的计算。那如何解决呢？其实我们可以使用迭代的方式进行计算：（从前往后算），还是求第10个斐波那契数：

代码如下：

//迭代求第n个斐波那契数
int fibonacci(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 fibonacci_number = fibonacci(n);printf("%d\n", fibonacci_number);return 0;
}

图解如下：

关于求解第n个斐波那契数的总结图：

题目五：

题目名称：
计算一个数的每位之和（递归实现）
题目内容：
写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
输入：1729，输出：19

题解：

  • 关注点应该在k次方上，当k为1次方时，无论n是什么数，结果都为1
  • 我们可以进行拆分，n^k --> n*n^k-1
  • 相当于n^1 * n^k-1,不断拆分下去，直到k<2，返回
  • 注意点：如果n == 1，那返回1
  • 看代码：
int Com_n_K(int n,int k)
{//当次方数<2时，结果为n本身if (k < 2){return n;}//当n==1时，k次方结果均为1if (n == 1){return 1;}//当次方>=2时，进行拆分，n^1 * n^k-1，持续拆分，直到k<2返回nif (k>=2){return Com_n_K(n, k - 1) * n;}}
int main()
{int n = 0;int k = 0;scanf("%d %d", &n,&k);printf("%d的%d次方是：%d\n", n,k, Com_n_K(n,k));return 0;
}

代码图解：

题目六：

题目名称：
计算一个数的每位之和（递归实现）
题目内容：
写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
输入：1729，输出：19

题解：

  • 当这个数的位数为个位时（小于10），那和为本身。
  • 列如这个数为1729，当这个数大于9时，那我们可以将这个数拆分成，172 + 9，计算172每一位之和再+9，如何将位数分离开来呢？
  • 1729%10 == 9,1729/10 = 172，按照这种规律，持续拆分下去，直到这个数只剩个位（小于10），开始回归。
  • 看代码：
int Sum_Mw(int n)
{//当n>9时，将n看成两部分，先计算除最后一位数的//每位之和，再加上最后一位数，持续拆分，直到n<10，回归n本身if (n>9){return Sum_Mw(n / 10) + n % 10;}return n;
}
int main()
{int n = 0;scanf("%d", &n);int sum = Sum_Mw(n);printf("%d\n", sum);return 0;
}

代码图解：

题目七：

题目：字符串逆序（递归实现）

题目内容：

编写一个函数 reverse_string(char * string)（递归实现）

实现：将参数字符串中的字符反向排列，不是逆序打印。

要求：不能使用C函数库中的字符串操作函数。

比如: char arr[] = "abcdef";

逆序之后数组的内容变成：fedcba

题解：

  • 既然要递归实现，那我们首先考虑递归的限制条件是什么
  • 限制条件为字符串的长度<=1时，递归结束，因为当字符串长度<=1时，可能是空字符串或者字符串中只有1个字符，这时进行返回即可，不需要进行逆序了。
  • 当字符串长度>1时，可以进行逆序操作。
  • 先模拟实现一个strlen函数，用来计算字符串的长度。
  • 然后创建一个临时变量存放头部字符，再进行与尾字符交换，这里与普通的交换不同，当最后一个字符的内容交换到头部字符后，下一步本该是将头部字符交换到末尾字符，但这里是先将末尾字符赋值成\0，而本该是末尾位置的字符存放在tmp临时变量中。
  • 为什么要先将末尾字符设置为\0呢，这是因为题目给出的函数只有一个参数，那就说明不能同时将头尾指针进行++，--操作了，那就先将头部字符暂时存储起来，让末尾字符变为\0，其实这步操作也相当于将尾指针--了，因为下一次操作时，末尾最后一个元素为前一个字符。
  • 解释清楚后，其实就是头指针++,尾指针--操作了，跟迭代思路一样，不断的循环，递归是不断的递归++，--。
  • 不断递归，当计算到字符串长度<=1时，就开始回归了。
  • 每回归一次后，将临时变量中的头部字符放置到末尾字符上，也就是之前设置成的\0位置。
  • 详细看代码：
//计算字符串长度， == strlen库函数
int Strlen_Ty(char* arr)
{int count = 0;char* Tmp_Arr = arr;while (*Tmp_Arr != '\0'){count += 1;Tmp_Arr += 1;}return count;
}
void reverse_string(char* string)
{//用于计算字符串长度的自定义函数int len = Strlen_Ty(string);//当字符串长度>1时if (len > 1){char tmp = *string;*string = *(string + len - 1);//将末尾字符，设置为\0，相当于让right--*(string + len - 1) = '\0';//递归//这里让string+1，相当于left+1reverse_string(string+1);//当递归结束，开始回归时，将尾指针修改为存在临时变量的头指针值*(string + len - 1) = tmp;}//当字符串长度<=1时，开始回归//情况1：只剩1个字符没逆序，而1个字符不需要逆序//情况2：空字符return;
}
int main()
{char arr[] = "abcdef";reverse_string(arr);printf("%s\n", arr);return 0;
}

代码图解：

总结

介绍完毕，希望能帮助到大家，后续还会出更多干货，关注我吧！！❤❤❤

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/304924.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Harmony鸿蒙南向驱动开发-GPIO接口使用

Harmony鸿蒙南向驱动开发-GPIO接口使用

功能简介 GPIO&#xff08;General-purpose input/output&#xff09;即通用型输入输出。通常&#xff0c;GPIO控制器通过分组的方式管理所有GPIO管脚&#xff0c;每组GPIO有一个或多个寄存器与之关联&#xff0c;通过读写寄存器完成对GPIO管脚的操作。 GPIO接口定义了操作GP…
阅读更多...
Day80：服务攻防-中间件安全HW2023-WPS分析WeblogicJettyJenkinsCVE

Day80：服务攻防-中间件安全HW2023-WPS分析WeblogicJettyJenkinsCVE

目录 中间件-Jetty-CVE&信息泄漏 CVE-2021-34429(信息泄露) CVE-2021-28169(信息泄露) 中间件-Jenkins-CVE&RCE执行 cve_2017_1000353 CVE-2018-1000861 cve_2019_1003000 中间件-Weblogic-CVE&反序列化&RCE 应用金山WPS-HW2023-RCE&复现&上线…
阅读更多...
windows ffmpeg7 通过rtsp拉取h265裸流

windows ffmpeg7 通过rtsp拉取h265裸流

点击下边那个链接会转到github 下载完成后&#xff0c;添加include、lib到工程。 添加头文件&#xff1a; extern "C" { #include "libavcodec/avcodec.h" #include "libavformat/avformat.h" #include "libavformat/avio.h" #inclu…
阅读更多...
Acrobat Pro DC 2021---PDF编辑与管理，打造高效PDF工作流程 含Mac+win

Acrobat Pro DC 2021---PDF编辑与管理，打造高效PDF工作流程 含Mac+win

Acrobat Pro DC 2021包括全面的PDF编辑、OCR识别、多种输出格式转换以及强大的文件安全性保护。用户可轻松编辑、合并、转换PDF文件&#xff0c;同时支持将扫描文档转换为可编辑的PDF。可将PDF转换为Word、Excel、PowerPoint等格式&#xff0c;提高工作效率。 Mac电脑&#xf…
阅读更多...
使用Docker部署开源项目FreeGPT35来免费调用ChatGPT3.5 API

使用Docker部署开源项目FreeGPT35来免费调用ChatGPT3.5 API

Vercel部署FreeGPT35有严重限制&#xff0c;玩玩就好&#xff0c;真用还是得docker。 限制原因: Vercel的流式响应并不是一开始写流&#xff0c;客户端就能立刻收到响应流&#xff0c;而是先写到一个缓冲区&#xff0c;当流关闭才一股脑的流式响应回来(不是实时流) 因此导致: …
阅读更多...
wireshark数据流分析学习日记day3-从 Pcap 导出对象

wireshark数据流分析学习日记day3-从 Pcap 导出对象

从 HTTP 流量导出文件 过滤http请求 发现get请求上传了两个文件 保存即可 也可以保存网页 点击保存 改文件名为html结尾以便于访问 请谨慎使用此方法。如果从 pcap 中提取恶意 HTML 代码并在 Web 浏览器中查看它&#xff0c;则 HTML 可能会调用恶意域&#xff0c;这就是为什么…
阅读更多...
android-自定义TextView在文字内容末尾添加图片icon、可以添加间距

android-自定义TextView在文字内容末尾添加图片icon、可以添加间距

样式示意图 自定义属性 style.xml <declare-styleable name"IconLabelTextView"><attr name"iconSrc" format"reference"/><attr name"iconPaddingStart" format"dimension"/><attr name"iconPad…
阅读更多...
【YOLOv8】Yolov5和Yolov8网络结构的分析与对比

【YOLOv8】Yolov5和Yolov8网络结构的分析与对比

目录 一 YOLOv5 二 YOLOv8 yolo通常采用backbone-neck-head的网络结构。 Backbone 主要负责从输入图像中提取高层次的语义特征,常包含多个卷积层和池化层&#xff0c;构建了一个深层次的特征提取器。Neck通常用来进一步整合与调整backbone提取的特征&#xff0c;有利于将不同…
阅读更多...
odoo10 创建第一个应用

odoo10 创建第一个应用

当odoo10环境创建好之后&#xff0c;需要设置一个用户 我这里设置的叫做odoo_user&#xff0c;并给他设置全部的权限&#xff0c;用于创建数据库。 当我们在odoo的web主页创建一个数据库&#xff0c;我这里叫做my_odoo&#xff0c;然后我们创建一个名为myapp的模块 python .…
阅读更多...
Linux云计算之Linux基础3——Linux系统基础part-2

Linux云计算之Linux基础3——Linux系统基础part-2

1、终端、shell、文件理论 1、终端 终端(terminal)&#xff1a;人和系统交互的必要设备&#xff0c;人机交互最后一个界面&#xff08;包含独立的输入输出设备&#xff09; 物理终端(console)&#xff1a;直接接入本机器的键盘设备和显示器虚拟终端(tty)&#xff1a;通过软件…
阅读更多...
知了汇智鸿蒙系列讲座进校园，赋能产业数字化升级，助力创新人才培养

知了汇智鸿蒙系列讲座进校园，赋能产业数字化升级，助力创新人才培养

随着信创国产化战略的深入推进&#xff0c;以及万物互联时代的加速到来&#xff0c;信息技术产业正迎来前所未有的发展机遇。在这一背景下&#xff0c;成都知了汇智科技有限公司作为产教融合领域的先行者&#xff0c;积极响应国家号召&#xff0c;通过举办鸿蒙系列讲座进校园活…
阅读更多...
对OceanBase中的配置项与系统变量，合法性检查实践

对OceanBase中的配置项与系统变量，合法性检查实践

在“OceanBase 配置项&系统变量实现及应用详解”的系列文章中&#xff0c;我们已经对配置项和系统变量的源码进行了解析。当涉及到新增配置项或系统变量时&#xff0c;通常会为其指定一个明确的取值范围或定义一个专门的合法性检查函数。本文将详细阐述在不同情境下&#x…
阅读更多...
【TB作品】MSP430单片机读取大气压强传感器BMP180

【TB作品】MSP430单片机读取大气压强传感器BMP180

文章目录 实物main所有代码 实物 main #include <msp430.h> #include "stdio.h" #include "OLED.h"#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>// P2.2 oled scl // P2.3 oled sda// p…
阅读更多...
【vue/uniapp】使用 smooth-signature 实现 h5 的横屏电子签名

【vue/uniapp】使用 smooth-signature 实现 h5 的横屏电子签名

通过github链接进行下载&#xff0c;然后代码参考如下&#xff0c;功能包含了清空、判断签名内容是否为空、生成png/jpg图片等。 签名效果&#xff1a; 预览效果&#xff1a; 下载 smooth-signature 链接&#xff1a;https://github.com/linjc/smooth-signature 代码参考&a…
阅读更多...
数据结构OJ题——栈和队列

数据结构OJ题——栈和队列

1. 用栈实现队列&#xff08;OJ链接&#xff09; 题目描述&#xff1a;请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09; void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回…
阅读更多...
SpringBoot快速入门笔记（5）

SpringBoot快速入门笔记（5）

文章目录 一、elemetnUI1、main.js2、App.vue3、fontAwesome 一、elemetnUI 开源前端框架&#xff0c;安装 npm i element-ui -S 建议查看官方文档 Element组件&#xff0c;这里是Vue2搭配elementUI&#xff0c;如果是vue3就搭配elementPlus&#xff0c;这里初学就以Vue2为例子…
阅读更多...
【软考---系统架构设计师】计算机网络章节

【软考---系统架构设计师】计算机网络章节

目录 一、TCP/IP协议族 &#xff08;1&#xff09;基本介绍 &#xff08;2&#xff09;TCP和UDP的区别 &#xff08;3&#xff09;DNS协议 &#xff08;4&#xff09;DHCP协议 二、网络规划与设计 &#xff08;1&#xff09;需求分析 &#xff08;2&#xff09;通信规范…
阅读更多...
Vue3（一）：win7使用vue-cli创建vue3工程

Vue3（一）：win7使用vue-cli创建vue3工程

一、资料分享 网课地址&#xff1a;尚硅谷Vue3入门到实战&#xff0c;最新版vue3TypeScript前端开发教程_哔哩哔哩_bilibili vuecli创建vue3项目官网&#xff1a;创建一个项目 | Vue CLI vite创建vue3官网&#xff1a;快速上手 | Vue.js 尚硅谷笔记&#xff1a;https://pan.ba…
阅读更多...
【GO语言卵细胞级别教程】11.探索Go语言的面向对象编程之美（含源码仅此一份，先到先得）

【GO语言卵细胞级别教程】11.探索Go语言的面向对象编程之美（含源码仅此一份，先到先得）

【GO语言卵细胞级别教程】11.探索Go语言的面向对象编程之美&#xff08;含源码仅此一份&#xff0c;先到先得&#xff09; 目录 【GO语言卵细胞级别教程】11.探索Go语言的面向对象编程之美&#xff08;含源码仅此一份&#xff0c;先到先得&#xff09;1.面向对象的引用1.1简介1…
阅读更多...
day55 最长递增子序列 最长连续递增子序列 最长重复子数组

day55 最长递增子序列 最长连续递增子序列 最长重复子数组

题目1 300 最长递增子序列 题目链接 300 最长递增子序列 题意 找到整数数组nums的最长严格递增子序列的长度&#xff08;子序列并不改变原始的顺序&#xff0c;但是可以删除元素&#xff09; 动态规划 动规五部曲 1&#xff09;dp数组及下标i的含义 dp[i] 表示以nums[i…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023