【C语言】函数递归详解

article/2025/9/12 4:39:55

函数递归

  • 1. 什么是函数递归
  • 2. 递归的两个必要条件
    • 2.1 练习1：打印一个数的每一位
    • 2.2 练习2：求字符串长度（strlen 模拟实现）
  • 3. 递归与迭代
    • 3.1练习3：求 n 的阶乘（不考虑溢出）
      • 3.1.1 递归求 n 的阶乘
      • 3.1.2 迭代（非递归）求n的阶乘
    • 3.2 练习4：求第 n 个斐波那契数（不考虑溢出）
      • 3.2.1 递归求第 n 个斐波那契数
      • 3.2.2 迭代（非递归）求第n个斐波那契数
  • 4.补充练习
    • 4.1 写一个函数实现n的k次方（递归实现）
    • 4.2 计算一个数的每位之和（递归实现）
    • 4.3 字符串逆序
      • 4.3.1 非递归实现字符串逆序
      • 4.3.2 递归实现字符串逆序

1. 什么是函数递归

程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小。

2. 递归的两个必要条件

(1) 存在限制条件，当满足这个限制条件的时候，递归便不再继续。
(2) 每次递归调用之后越来越接近这个限制条件

2.1 练习1：打印一个数的每一位

接受一个整型值（无符号），按照顺序打印它的每一位。

示例：
输入：1234，
输出： 1 2 3 4

思路：

  • 递归就是把大事化小，函数自己调用自己。
  • 按照顺序打印他的每一位，我们就用1234%10就会等于4，这样就打印出一个4了，那怎么打印其他的呢？123怎么来呢？1234/10=123,再继续123%10就等于3以此类推。
  • 这里我们写一个 print 函数，让print函数自己调用自己实现递归。if 语句判断 n 是否是个位数，当 n 是个位数就直接打印 n%10；当 n 不是个位数就先 n/10，再打印 n %10。

代码实现：

#include <stdio.h>
void print(unsigned int n)
{if (n > 9){print(n / 10);}printf("%d ", n % 10);
}
int main()
{unsigned int num = 0;scanf("%u", &num);print(num);//按照顺序打印num的每一位return 0;
}

在这里插入图片描述

图解：
在这里插入图片描述

2.2 练习2：求字符串长度（strlen 模拟实现）

编写函数不允许创建临时变量，求字符串的长度。

示例：
输入：abc
输出：3

思路：

  • 递归就是把大事化小，函数自己调用自己。
  • strlen 求字符串长度就是遇到 \0 才会停下。
  • 我们要计算一个字符串的长度，字符串为 abc，我们可以把 my_strlen(arr) 转化成：
    my_strlen(“abc”)
    1+my_strlen(“bc”)
    1+1+my_strlen(“c”)
    1+1+1+my_strlen(" ") //空字符里面有 \0

代码实现：

#include <stdio.h>
#include <string.h>
int my_strlen(char* str)
{if (*str != '\0')return 1 + my_strlen(str + 1);elsereturn 0;
}
int main()
{char arr[] = "abc";int len = my_strlen(arr);printf("%d\n", len);return 0;
}

图解：
在这里插入图片描述

3. 递归与迭代

3.1练习3：求 n 的阶乘（不考虑溢出）

示例:
输入：5
输出：120

3.1.1 递归求 n 的阶乘

在这里插入图片描述

这里只需要根据公式带进去写成函数，函数自己调用自己就可以了，这里不考虑溢出的情况。
代码实现：

//递归求n的阶乘
#include <stdio.h>
int Fac(int n)
{if (n <= 1)return 1;elsereturn n * Fac(n - 1);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fac(n);printf("%d\n", ret);return 0;
}

3.1.2 迭代（非递归）求n的阶乘

//迭代（非递归）求n的阶乘
#include <stdio.h>
int Fac(int n)
{int i = 0;int ret = 1;for (i = 1; i <= n; i++){ret = ret * i;}return ret;
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fac(n);printf("%d\n", ret);return 0;
}

总结：
一个问题既可以用递归的方式求解也可以用非递归的求解，非递归就是迭代，无论是递归的方式还是非递归的方式都很容易理解。迭代是指一件事情反复去做，但是迭代不一定是循环，循环是迭代的一种情况。

3.2 练习4：求第 n 个斐波那契数（不考虑溢出）

示例：
输入：10
输出：55

3.2.1 递归求第 n 个斐波那契数

斐波那契数列：（前两个数相加等于后面那个数）
1 1 2 3 5 8 13 21 34 55……

在这里插入图片描述

这里只需要根据公式带进去写成函数，函数自己调用自己就可以了，这里不考虑溢出的情况。
代码实现：

//递归实现
#include <stdio.h>
int Fib(int n)
{if (n <= 2)return 1;elsereturn Fib(n - 1) + Fib(n - 2);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);return 0;
}

但是我们发现有问题：
在使用 fib 这个函数的时候如果我们要计算第40个斐波那契数字的时候特别耗费时间。为什么呢？我们发现 fib 函数在调用的过程中很多计算其实在一直重复。我们将代码修改一下：

#include <stdio.h>
int count = 0;//全局变量
int Fib(int n)
{if (n == 3)count++;if (n <= 2)return 1;elsereturn Fib(n - 1) + Fib(n - 2);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);printf("count=%d\n",count);return 0;
}

在这里插入图片描述

看输出结果我们会发现 count 是一个很大很大的值。我们在计算第40个斐波那契数的时候第3个数重复计算了39088169次，第3个数被重复计算了这么多次，那第4 ，5，6等数也都会被重复计算很多次。这个程序的效率就会很低，因为重复计算的次数太多了。所以斐波那契数是不适合使用递归求解的，接下来试试非递归的求解。

3.2.2 迭代（非递归）求第n个斐波那契数

斐波那契数 1 1 2 3 5 8 13 21 34 55……
思路：
我们倒着往前算都是要知道前两个数的值，那么我们现在正着算。我们创建三个变量分别为 a,b,c。将他们都初始化为1，当 n = 1,n = 2时他们的斐波那契数都为1，所以我们只有当n>2的时候才要进行计算，c 的值等于a+b，c 计算完后将c的值赋给b，将 b 的值赋给 a。

代码实现：

//非递归求第n个斐波那契数
#include <stdio.h>
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;
}

我们将代码运行起来会发现结果可能是错的，但是速度大大的提升了。
当参数比较大，那就会报错： stack overflow（栈溢出）这样的信息。系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

提示：

  1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
  2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
  3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

4.补充练习

4.1 写一个函数实现n的k次方（递归实现）

示例：
输入：2
输出 ：8.000000

在这里插入图片描述
代码实现：

//递归实现n的k次方
#include <stdio.h>
double Pow(int n, int k)
{if (k > 0)return n * Pow(n, k - 1);else if (k == 0)return 1;elsereturn 1.0 / Pow(n, -k);//这种情况下返回的值是小数所以用double接收这个函数的返回值
}
int main()
{int n = 0;int k = 0;scanf("%d %d", &n, &k);double ret = Pow(n,k);printf("%lf\n", ret);return 0;
}

4.2 计算一个数的每位之和（递归实现）

写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和。
示例：调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19
输入：1729
输出：19

思路：我们将1729的每一位拆出来
DigitSum(1729)
DigitSum(172)+9
DigitSum(17)+9+2
DigitSum(1)+7+9+2

代码实现：

//计算一个数的每位之和（递归实现）
#include <stdio.h>
int DigitSum(unsigned int n)
{if (n < 10)return n;elsereturn DigitSum(n / 10) + n % 10;
}
int main()
{unsigned int num = 0;scanf("%u", &num);int sum = DigitSum(num);printf("%d\n", sum);return 0;
}

4.3 字符串逆序

编写一个函数 reverse_string(char * string)（递归实现）
实现：将参数字符串中的字符反向排列，不是逆序打印。
比如:

char arr[] = "abcdef";

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

4.3.1 非递归实现字符串逆序

下标法思路：

  • 数组arr[]=“abcdef”,我们发现逆序就是 a 和 f 交换，b 和 e 交换，c 和 d 交换，就是第一个字符和最后一个字符交换，第二个和倒数第二个交换，以此类推。
  • 我们现在就是要找到他们就能进行交换了，我们给一个左边的下标 left = 0 给 a；给一个右下标 right = len-1 给 f。让左右下标锁定两个元素进行交换，交换完成后 left++，right- -，然后重新锁定新的元素进行交换，以此类推。
    在这里插入图片描述

代码实现：

//下标法
#include <stdio.h>
#include <string.h>
void reverse_string(char* str)
{int len = 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);//fedcbareturn 0;
}

指针法思路：<指针法和下标法非常类似>
我们用一个 left 指针指向 a，用一个 right 指针指向 f ，然后再像前面下标法那样交换就可以了。

代码实现：

//指针法
#include <stdio.h>
#include <string.h>
void reverse_string(char* str)
{int len = strlen(str);char* left = str;char* right = str + len - 1;while (left < right){char tmp = *left;*left = *right;*right = tmp;left++;right--;}
}
int main()
{char arr[] = "abcdef";reverse_string(arr);printf("%s\n", arr);//fedcbareturn 0;
}

补充：

  • strlen 是库函数，是计算字符串长度的，只针对字符串，关注 \0 的位置，\0 之前出现多少个字符，字符串的长度就是多少。
  • sizeof 是操作符，是计算数据占用内存空间的大小，单位是字节，不在乎内存中存放的是什么。

4.3.2 递归实现字符串逆序

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

思路：把后面的字符赋值给前面的字符，后面的字符用\0覆盖

  • 第一步：先创建一个变量tmp,将我们的 a 取出存放在 tmp 里面；
  • 第二步：将后面的字符 f 存放在前面的字符 a 的位置（就是把 f 赋值给 a）；
  • 第三步：后面的字符 f 的位置用 \0 覆盖，然后逆序中间的字符 str+1 指向 b 的位置，逆序 bcde 字符；
  • 第四步：将 tmp 中的 a 存放到后面字符的位置 上，以此类推。
    在这里插入图片描述

代码实现：

//递归实现字符串逆序
#include <stdio.h>
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);char tmp = *str;*str = *(str + len - 1);*(str + len - 1) = '\0';if (my_strlen(str + 1) > 1)reverse_string(str + 1);*(str + len - 1) = tmp;}
int main()
{char arr[] = "abcdef";reverse_string(arr);printf("%s\n", arr);//fedcbareturn 0;
}

本章到这里就结束啦，如果有哪里写的不好的地方，请指正。
如果觉得不错并且对你有帮助的话请给个三连支持一下吧！
Fighting!!!✊


http://chatgpt.dhexx.cn/article/aDMX0dww.shtml

相关文章

C语言详解：函数递归专题

C语言详解：函数递归专题

文章目录 函数递归函数递归的定义和优缺点递归的使用场景及必要条件递归的细节说明递归的习题讲解1打印整数每一位输入输出示例解题思路代码逻辑 2递归和非递归求n阶乘输入输出示例解题思路代码逻辑 3strlen函数模拟输入输出示例解题思路代码逻辑 4逆序字符串输入输出示例解题思…
阅读更多...
2021-11-03

2021-11-03

**"21天好习惯"第一期—12**1.递归函数&#xff08;二&#xff09; 程序在计算5的阶乘的时候&#xff0c;先执行递推&#xff0c;当n1或者n0的时候返回1&#xff0c;再回推将计算并返回。由此可以看出递归函数必须有结束条件。 递归函数特点&#xff1a; 1.每一级…
阅读更多...
[C语言学习]----函数递归（超详细！！！）

[C语言学习]----函数递归（超详细！！！）

本篇介绍的是C语言函数递归的详细知识 程序的艺术来源于生活 目录 7. 函数递归 7.1递归是什么 7.2 递归的两个必要条件 7.2.1练习1&#xff08;详细讲解&#xff09; 7.2.2练习2&#xff08;详细讲解&#xff09; 7.3 递归与迭代 7.3.1练习3&#xff08;详细讲解&#xff…
阅读更多...
五、需求分析建模之数据库建模

五、需求分析建模之数据库建模

1. 了解E-R图在基于数据库的软件系统分析中的作用。 2. 复习并深化理解E-R图的相关概念。 3. 学习从实际应用问题中抽取E-R模型的方法。 4. 掌握简单ER图模型建模工具 E-R模型 Entity-Relationship Model E-R模型是一种数据建模的思想。 1. E-R模型的基本观点&#xff1a; 世…
阅读更多...
数据库设计（1）—需求分析

数据库设计（1）—需求分析

2019独角兽企业重金招聘Python工程师标准>>> 需求分析是设计数据库的起点&#xff0c;需求分析结果是否准确反映用户的实际要求将直接影响到后面各阶段的设计&#xff0c;并影响到设计结果是否合理实用。 一、需求分析的任务 需求的任务是通过详细调查现实世界要处理…
阅读更多...
SQL数据库设计（一）---需求分析与逻辑设计

SQL数据库设计（一）---需求分析与逻辑设计

今天先来介绍 数据库设计中的需求分析和逻辑设计(ER图)阶段&#xff0c;明天介绍物理设计与维护优化,数据库设计是非常有意思的:-) 数据库设计 根据系统业务的需要&#xff0c;结合我们所选用的DBMS&#xff0c;为这个业务系统构建出最优的数据存储模型。 并建立好数据库中的表…
阅读更多...
数据库设计2————需求分析

数据库设计2————需求分析

需求分析任务 1、信息需求。明确数据库需要存储的数据&#xff0c;对这些数据将哪些梳理&#xff0c;同时还要描述数据间的联系。 2、处理需求。定义系统数据处理的操作功能&#xff0c;描述操作的优先次序。包括操作的执行频率和场合&#xff0c;操作与数据间的联系&#xff…
阅读更多...
数据库设计(一) 需求分析

数据库设计(一) 需求分析

目前&#xff0c;大多数的应用系统都属于数据库应用程序&#xff0c;都离不开数据库的支持。数据库设计方案的优劣对于应用程序的运行至关重要。数据库设计过程就是针对具体的应用环境&#xff0c;设计优化的逻辑模式&#xff0c;并根据所采用的数据库系统设计物理结构&#xf…
阅读更多...
三、数据需求与数据库设计

三、数据需求与数据库设计

数据需求与数据库设计 数据需求 项目中主要包含了用户、权限&#xff08;菜单&#xff09;、角色三种类型的数据&#xff0c;各种数据包含的数据项如下&#xff1a; &#xff08;1&#xff09;用户&#xff1a;用户名、密码、生日、头像、简介、用户类型 &#xff08;2&…
阅读更多...
SQL数据库实战需求分析→数据库设计

SQL数据库实战需求分析→数据库设计

从这开始&#xff0c;就真正进入项目实战啦。先说点体会&#xff0c;我刚开始接触编程的时候&#xff0c;都是编写一些小东西&#xff0c;往往都是半天或者一天什么的就编完了&#xff0c;那时候根本没想过做程序之前还要有需求分析。经过快两年的学习&#xff0c;接触的都是比…
阅读更多...
数据库性能需求分析及评估模型

数据库性能需求分析及评估模型

数据库作为应用系统当中最重要的一块&#xff0c;也是性能测试非常关注的一块&#xff0c;根据我自己的项目经验&#xff0c;和以往对应用系统的性能需求分析和测试策略制定过程&#xff0c;总结一下如何开展数据库系统的性能需求分析&#xff0c;以及制定数据库能力评估模型。…
阅读更多...
互联网应用开发实践：需求分析与数据库设计

互联网应用开发实践：需求分析与数据库设计

在本文中将分析一个用于新生开学分配寝室的“宿舍秒杀”系统。从用户故事开始探索需求&#xff0c;进而分析得到系统的主要功能和非功能性需求。最后&#xff0c;根据需求分析设计数据库&#xff0c;数据库的设计原则是尽可能的方便之后的需求拓展和修改。 用户故事 用户故事一…
阅读更多...
数据库应用系统的需求分析

数据库应用系统的需求分析

一 需求分析的概念与意义 所谓的需求分析&#xff0c;就是对待开发系统要做什么&#xff0c;完成什么功能的全面描述 软件的一些特性使得需求的获取常常并不容易&#xff01; 比如软件功能复杂&#xff0c;需求可变性&#xff0c;软件的不可见性 二 获取需求的方法 面谈实地…
阅读更多...
数据库设计：需求分析

数据库设计：需求分析

设计一个性能良好的数据库系统&#xff0c;明确应用环境对系统的要求是首要的和基本的。因此&#xff0c;应该把对用户需求的收集和分析作为数据库设计的第一步。 需求分析的主要任务是通过详细调查要处理的对象&#xff0c;包括某个组织、某个部门、某个企业的业务管理等&…
阅读更多...
数据库设计 | 需求分析

数据库设计 | 需求分析

一、需求分析要干一个什么样的事情&#xff1f; 通过详细调查现实世界要处理的对象&#xff08;组织、部门、企业等&#xff09;&#xff0c; 充分了解原系统&#xff08;手工系统或计算机系统&#xff09;工作概况&#xff0c; 明确用户的各种需求&#xff0c;然后在此基础上确…
阅读更多...
数据库设计之需求分析

数据库设计之需求分析

需求分析简单地说就是分析用户的需求。根据分析是设计数据库的起点&#xff0c;需求分析结果是否准确反映用户的实际要求将直接影响到后面各阶段的设计&#xff0c;并影响到设计结果是否合理和实用。 1. 需求分析的任务 需求分析的任务是通过详细调查现实世界要处理的对象(组…
阅读更多...
数据库技术-数据库需求分析、数据流概念

数据库技术-数据库需求分析、数据流概念

目录 需求分析 数据流 结构化分析案例-教材销购案例 例题讲解 每文一语 需求分析 1、需求分析的概念与意义 需求是指用户对软件的功能和性能的要求&#xff0c;就是用户希望软件能做什么事情&#xff0c;完成什么样的功能&#xff0c;达到什么性能。 需求分析是在计算机…
阅读更多...
matlab gui 教学，新手入门教程（一）文本框和按钮的使用

matlab gui 教学，新手入门教程（一）文本框和按钮的使用

matlab gui 教学&#xff0c;新手入门教程&#xff08;一&#xff09;文本框和按钮的使用 一、新建文件二、添加控件 一、新建文件 1、在MATLAB命令行中输入guide。 2、回车&#xff0c;进入GUI的界面&#xff0c;选择新建GUI–Blank GUI(Default)–浏览&#xff08;自定义存储…
阅读更多...
零基础入门MATLAB（一篇十分钟）

零基础入门MATLAB（一篇十分钟）

目录 一、复数 二、取整函数 三、无穷量&#xff08;Inf&#xff09;和非数值量&#xff08;NaN&#xff09; 四、逻辑类型 五、字符和字符串 六、函数句柄 七、结构体 八、数组类型 九、单元数组 十、map容器类型 参考《MATLAB R2020a 完全自学一本通》 一、复数 …
阅读更多...
matlab如何使输出结果更美观(symdisp函数——pretty函数升级版)

matlab如何使输出结果更美观(symdisp函数——pretty函数升级版)

matlab中有些计算结果比较长&#xff0c;直接查看有些困难&#xff0c;下面介绍pretty和symdisp函数优化输出结果&#xff0c;使结果更为直观。 演示示例1 有一个计算结果如下&#xff1a; >> f1f1 y^5 (- w - y0)*y^4 1800*y^3 (1498200*w - 1800*y0)*y^2 (3600*w…
阅读更多...
推荐文章

Copyright @ 2022~2023