C语言:递归思想及实例详解

简介:在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。通过函数的自调用化繁为简。

递归可以说是编程中最神奇的一种算法。因为我们有时候可能不能完全明晰代码的运行过程,但是我们却知道代码可以跑出正确的结果。而当我们使用其他算法,我们必须将代码运行的每一个细节都弄清楚才能确保代码的正确性。这就是递归的神奇之处。

下面由浅入深对递归进行解析:

1.阶乘计算

相信这是每个人初学递归时都会遇到的问题。当然这也是最容易理解的一种递归,思路很简单:

如果要计算n的阶乘,我们可以先算出n-1的阶乘再乘上n,如果要计算n-1的阶乘,我们可以先算出n-2的阶乘再乘上n-1,依此类推,递归逐渐深入,我们只需要给出1的阶乘和0的阶乘,然后递归就会不断返回,最后算出n的阶乘。

这一点还是比较容易理解,此处不作赘述。

int f(int n)
{
	if (n == 0 || n == 1)
		return 1;
	else
		return n * f(n - 1);
}

2.爬楼梯

爬楼梯OJ
题目概述:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

这也是一个典型可以用递归解决的问题

思路:如果我们要到达n阶,我们可以从n-1阶往上跳一个台阶,或者从n-2阶往上跳2个台阶,我们可以想想是不是只有这两种情况?所以到达n阶的方法数量是不是就是到达n-1阶的方法数量和到达n-2阶的方法数量之和?答案是显然的。那么这个问题是不是就和第一个例题类似了,只是这里的递归分支了,但是本质上是相同的,我们只需要给出到达1阶和到达2阶的方法数量,递归就能返回到n阶的方法数量。

int climbStairs(int n){
    if(n==1)
    return 1;
    else if(n==2)
    return 2;
    else
    return climbStairs(n-1)+climbStairs(n-2);
}

 需要注意的是:这里给出的代码并不能通过,因为分支递归在递归层数过深的时候很容易超时,举个例子,我们要计算到达10阶的方法数,我们要算9阶和8阶.......

这里递归的时间复杂度是O(2^n),n过大时超时是必然的。如果要避免超时可以使用迭代(循环)代替递归。使用递归的优势是代码逻辑更加明了,而迭代的优势是速度更快,如果递归分支了那么迭代的优势会更加明显。

这里给出迭代的方法仅供参考,不作讨论

int climbStairs(int n){
    if(n==1)
    return 1;
    if(n==2)
    return 2;
    int a=1;
    int b=2;
    int c;
    while(n>=3)
    {
        c=a+b;
        a=b;
        b=c;
        n--;
    }
    return c;
}

 3.找最大值

要求很简单,写一个函数

int find(int*nums,int numsSize)

 要求返回nums数组的最大值。最简单的方法是定义一个max变量遍历nums并更新max最后返回即可。如果使用递归该怎么做呢?

思路:我们将nums平分为左右两个部分,记左半部分最大值为max1,右半部分最大值为max2,那么显然整个nums的最大值是max1和max2中较大的一个。那么同样的,max1和max2是如何得到的呢?我们将左右部分分别再次平分........不断进行下去,知道最后平分完之后一个元素单独组成一个部分,那么这个部分的最大值就是这个单独的元素

int max(int* nums, int numsSize)
{
	int right = numsSize - 1;
	if (right == 0)
		return nums[0];
	else
	{
		int mid = right / 2;
		return max(nums, mid + 1) > max(nums + mid + 1, right -mid)? max(nums, mid + 1): max(nums + mid + 1, right - mid);
	}
}

以下是一个示意图: 

 教学视频:

在这里强烈推荐一个视频,视频链接,看完这个视频会对递归以及接下来的问题有更深刻的认识

4.归并排序

从这个部分开始递归就上了一个档次,第三个问题其实是这个问题的铺垫

归并排序的原理:与第三个问题一样,将数组细分直到每个部分只有一个元素,此时每个部分可以看作升序,使用merge函数将两部分合并成一个升序的部分(merge函数是将[4,8,9,10,1,2,3]这样两个部分为升序的数组排成完全升序的数组,力扣上有类似的实现merge函数的OJ    合并两个有序数组,但是这里是仅处理一个数组,只需要进行一些细节处理就能转换成相同问题)

归并排序的实现

void sort(int* arr1, int left, int right)
{
	if (right == left)
		return;
	int mid = left + (right - left) / 2;
    //将左半部分排序
	sort(arr1, left, mid);

    //将右半部分排序
	sort(arr1, mid + 1, right);

    //将两个升序部分排成完全升序
	merge(arr1, left, mid, right);
}

merge的实现

void merge(int* arr, int start, int mid, int end)
{
	int* copy = (int*)malloc(sizeof(int) * (end -start+ 1));
	memcpy(copy, arr+start,(end-start+1)*sizeof(int));
	int count = start;
	int count1 = 0;
	int count2 = mid-start+1;
	while (count1 <= mid-start && count2 <= end-start)
	{
		if (copy[count1] <= copy[count2])
		{
			arr[count++] = copy[count1++];
		}
		else
		{
			arr[count++] = copy[count2++];
		}
	}
	if(count1==mid-start+1)
	{
		while (count2 <= end-start)
		{
			arr[count++] = copy[count2++];
		}
	}
	else
	{
		while (count1 <= mid-start)
		{
			arr[count++] = copy[count1++];
		}
	}
	free(copy);
}

在上边给出的教学视频里包含详细的动画展示,这里就不画图进行模拟了。

5.汉诺塔问题

有A、B、C三根柱子,初始状态A柱子上有若干个盘子,目标是将A上的所有盘子移动到C柱子上,并且小盘子在上,大盘子在下,与初始状态相同。移动过程中大盘子不能放在小盘子上。

我们设计一个函数

void hano(int n,char a,char b,char c)

很多人对函数的四个参数不理解,或者理解不深刻,包括一些博文对几个参数都没有很好的解释。在这里先进行一个简单的分析,在后面的代码中会深入剖析。

参数分析:

很明显n表示A柱子上有n个盘子,奇怪的是为什么要三个char类型变量???其实很简单,这里的三个char类型形参接收的分别常量'A' 'B' 'C'中的一个。这个函数的含义是:将a变量的柱子上的n-1个盘子移动到b变量的盘子上,再将a变量柱子上第n个(最大的)盘子移动到c变量柱子上,最后将b变量柱子上的n-1个盘子移动到c变量柱子上。举个例子:

hano(15,'B','A','C');

表示将B柱子上的14个盘子移动到A,再把B上最后一个盘子移动到C上,再把A上n-1个盘子移动到C上

但是n-1个盘子是不能直接移动的,所以具体是怎么移动的呢?

当n=2时,我们会使用这个函数

hano(2,'A','B','C');

这样n-1=1,我们每次只会移动一个盘子,就可以直接移动了。

当n=3时,我们需要把2个盘子从A移动到B上,于是我们使用

hano(n-1,'A','C','B');

那么怎么把2个盘子移动到B上?我们首先要把1个盘子移动到C上

那么对于n个盘子,我们的思路也一样

//move中的n表示的是 第n个盘子
void move(int n, char soure, char destination)
{
	printf("move %d from %c to %c\n", n, soure, destination);
}
void hano(int n,char a,char b,char c)
{
	if (n == 1)
	{
		move(1, a, c);
	}
	else
	{
        //将n-1个盘子从a移动到b上
        //问题:既然是从a到b,那么和第二个参数有什么关系呢?为什么需要第二个参数?
		hano(n - 1, a, c, b);

		move(n, a, c);//只有一个盘子了,直接打印出移动轨迹

		hano(n - 1, b, a, c);
	}
}

现在对代码中提出的问题进行解答:我们再hano函数中再次调用hano,三个参数的值是会来回hano知道这一步的三hano才能推测下一步的三个参数,少一个参数hano函数就不能正常递归了

 

到了这里文章就结束了,最后再次推荐大家看一看文章给出的视频,看完会对递归有更深刻的认识。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

自动驾驶攻城战,华为小鹏先亮剑

点击关注 文&#xff5c;刘俊宏 编&#xff5c;苏扬、王一粟 本文为光锥智能x腾讯科技联合出品 2023年过半&#xff0c;城市NOA&#xff08;城市领航辅助驾驶&#xff09;的元年如预期中到来了吗&#xff1f; 8月25日&#xff0c;成都车展开幕&#xff0c;与4个月之前的上海…

(笔记五)利用opencv进行图像几何转换

参考网站&#xff1a;https://docs.opencv.org/4.1.1/da/d6e/tutorial_py_geometric_transformations.html &#xff08;1&#xff09;读取原始图像和标记图像 import cv2 as cv import numpy as np from matplotlib import pyplot as pltpath r"D:\data\flower.jpg&qu…

[PyTorch][chapter 53][Auto Encoder 实战]

前言&#xff1a; 结合手写数字识别的例子&#xff0c;实现以下AutoEncoder ae.py: 实现autoEncoder 网络 main.py: 加载手写数字数据集&#xff0c;以及训练&#xff0c;验证&#xff0c;测试网络。 左图&#xff1a;原图像 右图&#xff1a;重构图像 ----main----- 每轮训…

【哈士奇赠书活动 - 37期】- 〖深入浅出SSD:固态存储核心技术、原理与实战 第2版〗

文章目录 ⭐️ 赠书 - 《深入浅出SSD&#xff1a;固态存储核心技术、原理与实战 第2版》⭐️ 内容简介⭐️ 作者简介⭐️ 编辑推荐⭐️ 赠书活动 → 获奖名单 ⭐️ 赠书 - 《深入浅出SSD&#xff1a;固态存储核心技术、原理与实战 第2版》 ⭐️ 内容简介 本书从基础认知、核心技…

快速制作餐厅签到抽奖营销活动,吸引更多顾客

在如今竞争激烈的市场中&#xff0c;吸引用户参与活动是企业获取关注和提升转化率的重要手段。而签到抽奖活动无疑是一种简单而又有效的方式。本文将教你如何利用乔拓云平台后台制作一个快速而有效的签到抽奖活动。 首先&#xff0c;登录乔拓云平台后台&#xff0c;进入【营销活…

【云原生进阶之PaaS中间件】第一章Redis-2.3.3集群模式

1 集群模式 Redis集群是一个提供在多个Redis节点之间共享数据的程序集。它并不像Redis主从复制模式那样只提供一个master节点提供写服务,而是会提供多个master节点提供写服务,每个master节点中存储的数据都不一样,这些数据通过数据分片的方式被自动分割到不同的master节点上…

香橙派OrangePi zero H2+ 驱动移远4G/5G模块

目录 1 安装系统和内核文件&#xff1a; 1.1 下载镜像 1.2 内核头安装 1.2.1 下载内核 1.2.2 将内核头文件导入开发板中 1.2.3 安装内核头 2 安装依赖工具&#xff1a; 2.1 Installing Required Host Utilities 3 驱动步骤&#xff1a; 3.1 下载模块驱动文件…

IO模型:阻塞和非阻塞

一、五种IO模型------读写外设数据的方式 阻塞: 不能操作就睡觉 非阻塞&#xff1a;不能操作就返回错误 多路复用&#xff1a;委托中介监控 信号驱动&#xff1a;让内核如果能操作时发信号&#xff0c;在信号处理函数中操作 异步IO&#xff1a;向内核注册操作请求&…

5G NR:PRACH时域资源

PRACH occasion时域位置由高层参数RACH-ConfigGeneric->prach-ConfigurationIndex指示&#xff0c;根据小区不同的频域和模式&#xff0c;38.211的第6.3.3节中给出了prach-ConfigurationIndex所对应的表格。 小区频段为FR1&#xff0c;FDD模式(paired频谱)/SUL&#xff0c;…

CSRF(跨站请求伪造)和SSRF(服务端请求伪造)漏洞复现:风险与防护方法

这篇文章旨在用于网络安全学习&#xff0c;请勿进行任何非法行为&#xff0c;否则后果自负。 环境准备 一、CSRF&#xff08;跨站请求伪造&#xff09; 示例&#xff1a;假设用户在银行网站A上登录并保持会话活动&#xff0c;同时他也在浏览其他网站。攻击者在一个不可信任…

AMBA_AXI Protocol_基本读写事务

基本读写事务 1. 握手的过程 2. 信道信令要求 3. 通道之间的关系1. 握手的过程 当地址、数据或控制信息可用时&#xff0c;源端&#xff08;source&#xff09;产生VALID信号。终端&#xff08;destination&#xff09;生成READY信号&#xff0c;表示它可以接受该信息。传输只…

微前端:重塑大型项目的前沿技术

引言 随着互联网技术的飞速发展&#xff0c;前端开发已经从简单的页面制作逐渐转变为复杂的应用开发。在这个过程中&#xff0c;传统的前端开发模式已经难以满足大型项目的需求。微前端作为一种新的前端架构模式&#xff0c;应运而生&#xff0c;它旨在解决大型项目中的前端开…

Docker从认识到实践再到底层原理(一)|技术架构

前言 那么这里博主先安利一些干货满满的专栏了&#xff01; 首先是博主的高质量博客的汇总&#xff0c;这个专栏里面的博客&#xff0c;都是博主最最用心写的一部分&#xff0c;干货满满&#xff0c;希望对大家有帮助。 高质量博客汇总 然后就是博主最近最花时间的一个专栏…

适应高速率网络设备的-2.5G/5G/10G网络变压器/网络滤波器介绍

Hqst盈盛&#xff08;华强盛&#xff09;电子导读&#xff1a;在高速发展的互联网/物联网时代&#xff0c;为满足高网速的网络数据传输需求&#xff0c;网络设备在制造中也要选用合适的网络变压器/滤波器产品&#xff0c;有哪些可供选择的高速率网络变压器产品也是广大采购人员…

javaee spring 自动注入,如果满足条件的类有多个如何区别

如图IDrinkDao有两个实现类 方法一 方法二 Resource(name“对象名”) Resource(name"oracleDrinkDao") private IDrinkDao drinkDao;

异步迭代器

一、什么是异步迭代器&#xff1f; 实现了 __aiter__() 和 __anext__() 方法的对象。__anext__ 必须返回一个 awaitable对象。async for 会处理异步迭代器的 __anext__() 方法所返回的可等待对象&#xff0c;直到其引发一个 StopAsyncIteration 异常。 二、实例 class Async…

LeetCode239.滑动窗口最大值

看到这道题我就有印象&#xff0c; 我在剑指offer里面做过这道题&#xff0c;我记得当时用的是优先队列&#xff0c;然后我脑子里一下子就有了想法&#xff0c;拿优先队列作为窗口&#xff0c;每往右移动一步&#xff0c;把左边的数remove掉&#xff0c;把右边的数add进来&…

SpringAOP详解(下)

proxyFactory代理对象创建方式和代理对象调用方法过程&#xff1a; springaop创建动态代理对象和代理对象调用方法过程&#xff1a; 一、TargetSource的使用 Lazy注解&#xff0c;当加在属性上时&#xff0c;会产生一个代理对象赋值给这个属性&#xff0c;产生代理对象的代码为…

Linux系统下vim常用命令

一、基础命令&#xff1a; v:可视模式 i:插入模式 esc:命令模式下 :q &#xff1a;退出 :wq &#xff1a;保存并退出 ZZ&#xff1a;保存并退出 :q! &#xff1a;不保存并强制退出二、在Esc下&#xff1a; dd : 删除当前行 yy:复制当前行 p:复制已粘贴的文本 u:撤销上一步 U:…

IC芯片 trustzone学习

搭建Airplay TA环境需要在IC的TrustZone中进行。TrustZone是一种安全技术&#xff0c;用于隔离安全和非安全环境&#xff0c;并保护敏感文件。在TrustZone中&#xff0c;我们需要编写一个叫做TA&#xff08;Trusted Application&#xff09;的应用程序来控制这些私密文档。 &am…