重生之我在异世界学编程之C语言:深入函数递归篇

server/2024/12/14 10:36:11/

大家好,这里是小编的博客频道
小编的博客:就爱学编程

很高兴在CSDN这个大家庭与大家相识,希望能在这里与大家共同进步,共同收获更好的自己!!!

函数递归与迭代

  • 引言
  • 正文
    • 一、递归的基本概念
    • 二、递归的基本要素
    • 三、递归的优缺点
      • (1)优点
      • (2)缺点
    • 四、递归的应用场景
    • 五、C语言中的递归示例
      • 1. 计算阶乘
      • 2. 计算斐波那契数列
      • 3. 汉诺塔问题
    • 六、递归的常见问题和解决方法
      • (1)栈溢出
      • (2)重复计算
      • (3)难以理解的递归逻辑
    • 七、递归与迭代的比较
      • (1)优点对比
      • (2)缺点对比
  • 快乐的时光总是短暂,咱们下篇博文再见啦!!!不要忘了,给小编点点赞和收藏支持一下,在此非常感谢!!!

引言

递归(Recursion)是计算机科学中的一个重要概念,它指的是一个函数直接或间接地调用自身的方法。那现在宝子们就跟着小编的步伐一起进入本章知识的学习。Go!Go!Go!

在这里插入图片描述


那接下来就让我们开始遨游在知识的海洋!

正文


一、递归的基本概念

递归(Recursion)是计算机科学中的一个重要概念,它指的是一个函数直接或间接地调用自身的方法。在递归函数中,有一个明确的终止条件(也称为基准情形或基线条件),当满足这个条件时,递归将停止,从而防止无限循环的发生

递归通常用于解决那些可以分解为相似子问题的问题,通过将大问题分解为小问题来解决,这些小问题又可以进一步分解,直到达到一个可以直接解决的简单情况为止


二、递归的基本要素

递归函数这是实现递归的核心部分,即一个函数调用自身的函数

基准情形这是递归结束的条件。如果没有基准情形,递归将永远进行下去,导致栈溢出错误

递归步骤这是函数调用自身的部分,它将问题分解为更小的子问题


三、递归的优缺点

(1)优点

简洁性对于某些问题,递归提供了一种非常简洁和直观的解决方案

可读性递归代码往往更容易理解,特别是对于那些具有自然递归结构的问题

(2)缺点

性能问题由于每次递归调用都会占用一定的内存空间(主要是栈空间),因此递归算法可能会导致较高的时间和空间复杂度

调试困难递归算法的调试相对复杂,因为需要跟踪多个层次的函数调用

栈溢出风险如果递归深度过大,可能会耗尽系统的栈空间,导致程序崩溃


四、递归的应用场景

数学计算如阶乘、斐波那契数列等

数据结构操作如树的遍历(前序、中序、后序)、图的深度优先搜索(DFS)等

分治算法如归并排序、快速排序等

回溯算法如八皇后问题、数独求解等


五、C语言中的递归示例

1. 计算阶乘

阶乘是一个典型的递归问题。n的阶乘(记作n!)定义为从1到n的所有整数的乘积。特别地,0的阶乘被定义为1(0!=1)

#include <stdio.h>// 递归函数计算阶乘
int factorial(int n) {if (n == 0) { // 基准情形return 1;} else { // 递归步骤return n * factorial(n - 1);}
}int main() {int num = 5;printf("Factorial of %d is %d
", num, factorial(num));return 0;
}
  • 在这个例子中, factorial 函数通过递归调用自身来计算n的阶乘。当n为0时,函数返回1作为基准情形的结果;否则,函数返回n乘以 factorial(n-1) 的结果。

2. 计算斐波那契数列

斐波那契数列也是一个经典的递归问题。斐波那契数列的定义如下:F(0)=0,F(1)=1,对于n≥2,F(n)=F(n-1)+F(n-2)。

#include <stdio.h>// 递归函数计算斐波那契数列
int fibonacci(int n) {if (n == 0) { // 基准情形return 0;} else if (n == 1) { // 另一个基准情形return 1;} else { // 递归步骤return fibonacci(n - 1) + fibonacci(n - 2);}
}int main() {int num = 10;printf("Fibonacci number at position %d is %d
", num, fibonacci(num));return 0;
}
  • 在这个例子中, fibonacci 函数通过递归调用自身来计算斐波那契数列的第n项。当n为0或1时,函数分别返回0和1作为基准情形的结果;否则,函数返回 fibonacci(n-1) 加上fibonacci(n-2)的结果。

然而,需要注意的是:

  • 这种简单的递归方法在计算较大的斐波那契数时会变得非常低效因为它会重复计算许多相同的子问题。为了优化这个问题,可以使用动态规划或记忆化递归来避免重复计算

3. 汉诺塔问题

汉诺塔问题是另一个经典的递归问题。问题描述如下:有三根柱子A、B、C,其中A柱子上从上到下叠放着n个不同大小的圆盘,这些圆盘可以按照大小顺序在任何一根柱子的顶部移动,但在任何时候都不能把较大的圆盘放在较小的圆盘上。目标是将所有圆盘从A柱子移动到C柱子,并且每次只能移动一个圆盘。

分析:

(1)我们先分析1个盘子的时候:1个盘子我们直接把它从a柱移到c柱
(2)2个盘子:我们先把小的盘子从a柱移到b柱,再把大的盘子先从a柱移到c柱,最后把小的盘子从b柱移到c柱
(3)3个盘子:我们先把小的盘子从a柱移到c柱,再把中盘从a柱移至b柱,再把小盘从c柱移至b柱,再把大盘从a柱移至c柱,再把小盘从b柱移至a柱,再把中盘从b柱移至c柱,最后把小盘从a柱移至c柱
(4)综合分析:如果一个盘子,直接从a柱(起始柱)移到c柱(目标柱);如果是两个盘子,要先把(2 - 1)个盘子(最大盘子上的盘子)从a柱(起始柱)移到b柱(中转柱),再把[2 - (2 - 1) ]个盘子(最大的盘子)从a柱(起始柱)移到c柱(目标柱),最后把(2 - 1)个盘子从b柱(中转柱也是起始柱)移到c柱(目标柱);如果是三个盘子,要先把(3 - 1)个盘子从a柱移到b柱(这里的步骤参考前一个讨论),再把最大的盘子从a柱移到c柱,最后把(3 - 1)个盘子从b柱移到c柱(这里的步骤自己考虑,也就是类比);我们现在推广到n(n > 1)个盘子,就不难想到把(n - 1)个盘子先从a柱移到b柱(如果(n - 1)> 1就会借用c柱,否则不会),再把最大的盘子从a柱移到c柱,最后把n - 1个盘子从b柱移到c柱(借用与否参考前面)

用代码实现:

#include <stdio.h>// 递归函数解决汉诺塔问题
void hanoi(int n, char from_peg, char to_peg, char aux_peg) {if (n == 1) { // 基准情形printf("Move disk 1 from peg %c to peg %c
", from_peg, to_peg);return;}// 递归步骤:先将n-1个圆盘从from_peg移动到aux_peg,以to_peg为辅助柱hanoi(n - 1, from_peg, aux_peg, to_peg);// 将第n个圆盘从from_peg移动到to_pegprintf("Move disk %d from peg %c to peg %c
", n, from_peg, to_peg);// 最后将n-1个圆盘从aux_peg移动到to_peg,以from_peg为辅助柱hanoi(n - 1, aux_peg, to_peg, from_peg);
}int main() {int num_disks = 3;hanoi(num_disks, 'A', 'C', 'B');return 0;
}

在这个例子中, hanoi 函数通过递归调用自身来解决汉诺塔问题。当n为1时,函数直接打印出移动圆盘的指令作为基准情形的结果;否则,函数首先递归地将n-1个圆盘从起始柱子移动到辅助柱子(以目标柱子为辅助)然后将第n个圆盘从起始柱子移动到目标柱子最后再次递归地将n-1个圆盘从辅助柱子移动到目标柱子(以起始柱子为辅助)


六、递归的常见问题和解决方法

(1)栈溢出

原因:

  • 递归深度过大,导致系统栈空间耗尽。

解决方法:

  • 增加系统栈的大小(不推荐,因为这可能导致其他问题);使用迭代算法代替递归算法;或者使用尾递归优化(但C语言标准并不保证对尾递归进行优化)。

(2)重复计算

原因:

  • 递归算法在求解过程中可能会多次计算相同的子问题。

解决方法:

  • 使用动态规划或记忆化递归来存储已经计算过的子问题的结果,以避免重复计算。

(3)难以理解的递归逻辑

原因:

  • 递归算法的逻辑可能比较复杂,特别是对于初学者来说。

解决方法:

通过绘制递归树、使用纸笔模拟递归过程或使用调试工具逐步跟踪递归调用的执行过程来帮助理解递归逻辑。


七、递归与迭代的比较

递归和迭代是解决问题的两种基本方法。它们各有优缺点,适用于不同类型的问题。

(1)优点对比

递归:

代码更简洁、更易读(特别是对于具有自然递归结构的问题)。 更容易理解和实现复杂的算法(如分治算法、回溯算法等)

迭代:

通常比递归更高效,因为不需要额外的函数调用开销。 更容易控制程序的执行流程(如循环次数、中断条件等)

(2)缺点对比

递归:

可能导致栈溢出错误(特别是当递归深度很大时)。 对于某些问题,递归逻辑可能比迭代更难理解和实现

迭代:

对于某些具有自然递归结构的问题,迭代算法可能更复杂且不易于理解。 需要显式地管理循环变量和状态信息(这可能会增加代码的复杂性)


快乐的时光总是短暂,咱们下篇博文再见啦!!!不要忘了,给小编点点赞和收藏支持一下,在此非常感谢!!!


http://www.ppmy.cn/server/150069.html

相关文章

vue3+setup使用rtsp视频流实现实时监控,全屏,拍摄,自动拍摄等功能(纯前端)

vue3setup使用rtsp视频流实现实时监控&#xff0c;全屏&#xff0c;拍摄&#xff0c;自动拍摄等功能(纯前端) 概要 本文介绍了如何在Vue应用中通过WebRTC技术获取摄像头的rtsp视频流&#xff0c;同时展示了实时监控&#xff0c;全屏&#xff0c;拍摄&#xff0c;自动拍摄等功…

利用GeoWave导入矢量数据到HBase/Accumulo数据库

前言 最近在做有关地理时空大数据的实验&#xff0c;本文将介绍如何利用geowave框架&#xff0c;将矢量数据导入到HBase或Accumulo等NoSQL数据库中。 软件版本&#xff1a; Hadoop: 2.10.2 Zookeeper: 3.6.4 geowave: 1.2.0 Accumulo&#xff1a;1.9.3 HBase: 1.4.0 Ja…

MongoDB-单键索引与复合索引

在 MongoDB 中&#xff0c;索引是提高查询性能的一个重要手段。通过为集合中的字段创建索引&#xff0c;可以显著加快对数据的检索速度。MongoDB 支持多种类型的索引&#xff0c;其中 单键索引 和 复合索引 是最常用的两种类型。了解这两种索引的工作原理、使用场景以及区别&am…

本地体验新版springcloud-搭建工程学习笔记

为了快速体验下新版本springcloud.对照b站图灵视频简单记录下。起码入门不要钱&#xff0c;值得推荐。 基础知识&#xff1a; 会用springboot写demo。 会用mybatis操作MYSQL。 会用git拉取代码。 这都是基本操作。 环境准备&#xff1a; jdk17 demo是21.我实际测试17也可…

Nginx之配置防盗链(Configuring Anti-hotlinking in Nginx)

运维小白入门——Nginx配置防盗 什么是防盗链&#xff1a; 防盗链技术主要用于防止未经授权的第三方或域名访问网站的静态资源。例如&#xff0c;一个网站可能拥有独特的图片素材&#xff0c;为了防止其他网站通过直接链接图片URL的方式访问这些图片&#xff0c;网站管理员会采…

MedLSAM: 用于3D CT图像的局部化和分割模型|文献速递-生成式模型与transformer在医学影像中的应用

Title 题目 MedLSAM: Localize and segment anything model for 3D CT images MedLSAM: 用于3D CT图像的局部化和分割模型 01 文献速递介绍 最近&#xff0c;计算机视觉领域对开发大规模的基础模型的兴趣不断增加&#xff0c;这些模型能够同时处理多个视觉任务&#xff0c…

常见的网络命令

目录 1. ping2. netstat3. pidof 1. ping ping 命令可以用于检查两台主机是否连通&#xff08;是否可以进行通信&#xff09; ping -cn ip/域名 -cn: 指定 ping 的次数 n2. netstat netstat&#xff1a;一个查看网络状态的工具&#xff0c;常用于监听 常用选项 -n 拒绝显示别名…

pcl::PointCloud<pcl::PointXYZ>和pcl::PointCloud<pcl::PointXYZ>::Ptr 转换及新建点云显示

点云智能指针格式和非指针格式的转换 pcl::PointCloud<PointT>::Ptr cloud_ptr(new pcl::PointCloud<PointT>); pcl::PointCloud<PointT> cloud; cloud *cloud_ptr; cloud_ptr boost::make_shared<pcl::PointCloud<PointT>>(cloud);全部代码&…