C语言学好递归看这一篇就够了

前言

在一定的时间、空间限制下，人的体力有限，思维力也有限，递归思维对实践最有用的指导，就是把脑力集中于定义问题这个关键点上，不用去找解题的过程。定义（问题）即解决（问题），定义即解决！ 让大问题变成规模更小的问题并立即获得解决，以此作为基础，让我们轻松解决函数本身定义的问题。所以，递归在编程中同样是很重要的一个知识点。

提示：以下是本篇文章正文内容

一、递归是什么？

先来看一下定义：

程序调用自身的编程技巧称为递归（ recursion）。

简单来说，就是在一个函数里面调用函数自己本身。

举个例子：
用递归实现求第n个斐波那契数。

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

int main()
{
	//斐波那契数 1 1 2 3 5 8 13 21 34 51....,除前两位外，后一个数的值等于前两位相加
	int n = 0;
	printf("请输入你要查找的斐波那契数：");
	scanf("%d", &n);
	int ret=Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

所以，我们可以看到，所谓递归，其实就是一个函数里面调用函数自己本身。具体怎样调用的，我们下面再讲。

二、递归的两个必要条件

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

分析之后，我们可以得出两个点

1、结束条件
2、逼近条件

我们在使用递归的时候，需要满足这两个条件。

总结起来四个字——大事化小

继续举斐波那契数的例子：

三、递归是怎样运行的

我们通过一道题目来讲解。

题目： 递归实现n的k次方
内容： 编写一个函数实现n的k次方，使用递归实现。

【解决思路】
运用递归思路，我们只要找到递归结束条件和逼近条件。通过分析，我们可以画出下面这幅图。

【代码实现】

#include <stdio.h>
double power(int n,int k)
{
	if (k< 0)
	{
		k = -k;
		return 1 / (n*power(n, k - 1));
	}
	else if (k == 0)
		return 1;
	else if (k>0)
	{
		return n * power(n, k - 1);
	}
}
int main()
{
	int n = 0;
	int k = 0;
	printf("请输入一个整数：");
	scanf("%d", &n);
	printf("请输入要求的次方数：");
	scanf("%d", &k);
	double ret=power(n,k);
	printf("%1f\n", ret);
	return 0;
}

【画图详解递归思路】

通过图解，发现思路，我们** 存在限制条件k，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。**之后输出的时候就反过来回去。

这个就是递归的思路。

四、迭代与递归

不知大家有没有认真思考过上面的求斐波那契数的代码，它有什么问题？

如果我们这里求的是第50个斐波那契数呢？大家可以运行一下代码。可以发现，电脑运行了好久好久才算出结果，费时间。
如果求第10000个斐波那契数呢？程序就会崩溃。

为什么呢？
我们发现上面求斐波那契数的 Fib 函数 在调用的过程中很多计算其实在一直重复。
因为我们在调用这个函数的时候，除前两位外，后一个数的值等于前两位相加。这就导致了我们不断重复计算

如图：

我们可以看到，由于前两个数相加等于后一个数，前两个数相加等于后一个数，所以我们会不断产生重复的计算。就会造成计算量非常大，效率极低。

那我们如何改进呢？
我们程序存东西的时候，存放在栈区。
如图：

在调试 例子中的Fib函数的时候，如果你的参数比较大，那就会报错： `stack overflow（栈溢出） 这样的信息。
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

那如何解决上述的问题：

将递归改写成非递归。使用static对象替代non-static局部对象。在递归函数设计中，可以使用static对象替代nonstatic局 部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销，
而且static对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。

这里我们介绍迭代。

什么是迭代呢？
【概念】

迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值。

借用网上的图片来说明（侵删）

目前对于c语言来说，迭代可以简单认为是循环结构。

那么我们如何用迭代的方式求斐波那契数呢？
【代码如下】

int Fib(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n>2)
	{
		c = a + b;//求出c的值
		a = b;//a赋值给b,也就是a作为b的值
		b = c;//b赋值给c，也就是b作为c的值
		n--;
	}
	return c;
}

int main()
{
	// 1 1 2 3 5 8 13 21 34 55,除前两位外，后一个数的值等于前两位相加
	int n = 0;
	printf("请输入你要查找的斐波那契数：");
	scanf("%d", &n);
	int ret = Fib(n);
	printf("你好，你要需要的值是：%d\n", ret);
	return 0;
}

这样，我们算很大的数都能一下子算出来了，虽然不能保证正确，因为栈溢出了，但是效率很快。

五、递归与迭代的比较

我们用一个表格来分析：

【注意】

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

六、 什么时候用递归

什么时候用递归呢？

（1）当解决一个问题时，递归和非递归都可以使用，且没有明显问题，那就可以使用递归
（2）当解决一个问题时，递归写起来很简单，非递归比较复杂，且递归没有明显问题，那就用递归
（3）如果说，用递归解决问题，写起来简单，但是有明显问题，那就不能使用递归

最后

以上内容是通过本人学习的理解和网上资料的整理梳理出来的递归与迭代的一些内容，有错漏之处，还请各位多多包涵与指出，共同进步，共同成长!

到此这篇关于C语言学好递归看这一篇就够了的文章就介绍到这了,更多相关C语言 递归内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言函数的基本使用和递归详解

    C语言函数的基本使用和递归详解

    目录 本章目标 函数是什么 C语言中函数的分类 库函数 如何学会使用库函数? 自定义函数 函数的参数 函数的调用: 函数的嵌套调用和链式访问 嵌套调用 链式访问 函数的声明和定义 函数递归 什么是递归? 递归的两个必要条件 递归与迭代 总结 本章目标 秃头侠们好呀,今天我们一起学习函数! 目标: 本章主要掌握函数的基本使用和递归 函数是什么 数学中我们常见到函数的概念.但是你了解C语言中的函数吗? 维基百科中对函数的定义:子程序 在计算机科学中,子程序(英语:Subroutine, proced

  • C语言递归之汉诺塔和青蛙跳台阶问题

    C语言递归之汉诺塔和青蛙跳台阶问题

    递归就是一个函数执行过程中调用自己,在c语言中有很多关于递归的经典问题,例如:斐波那契数列问题.汉诺塔问题等,在研究递归问题时我们要注意三点: 1.递归的结束条件 2.递归在每次进行过程中,都得离条件越来越近 3.相邻两次递归调用之间的关联关系 汉诺塔问题: 有三根杆子A, B, C.A杆上有N个(N > 1)穿孔圆盘, 盘的尺寸由下到上依次变小.要求按下列规则将所有圆盘移至C杆: 1.每次只能移动一个圆盘: 2.大盘不能叠在小盘上面,可将圆盘临时置于B杆, 也可将从A杆移出的圆盘重新移回A杆,

  • C语言函数的基本使用和递归小结

    C语言函数的基本使用和递归小结

    本章目标 秃头侠们好呀,今天我们一起学习函数! 目标: 本章主要掌握函数的基本使用和递归 函数是什么 数学中我们常见到函数的概念.但是你了解C语言中的函数吗? 维基百科中对函数的定义:子程序 在计算机科学中,子程序(英语:Subroutine, procedure, function, routine, method,subprogram, callable unit),是一个大型程序中的某部分代码, 由一个或多个语句块组成.它负责完成某项特定任务,而且相较于其他代 码,具备相对的独立性. 一般

  • C语言递归实现扫雷游戏

    C语言递归实现扫雷游戏

    前言 首先要实现扫雷原理上同三子棋,都是通过一个二维数组来实现游戏主题功能那么这里有几个值得注意的点 1.初级扫雷我们知道是九乘九数组实现,那么在这里我们创建的是11乘11的数组,目的是方便后续判断周围九个格子的雷的数量! 2.而且我们需要创建两个数组,一个用来存放字符1和0(1表示有雷,随机数生成:0表示没雷,初始化时自动全放0): 另一个用来根据上边的数组输出显示玩家是否被炸死,以及玩家选择的坐标周围雷的数量 3.需要注意排雷时候如果附近没有雷需要递归展开!!! 4.我们这里需要两个源文件t

  • C语言中递归的实际应用与经典问题

    C语言中递归的实际应用与经典问题

    目录 一.什么是递归 二.递归模板 三.递归的实际应用 1.阶乘递归 2.斐波那契数列 四.递归的经典问题 汉诺塔问题 青蛙跳台阶 总结 一.什么是递归 递归简单的来说就是在函数中调用自己 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量. 递归的两个必要条件: 存在限制条件,当满足这个限制条件的时候,递归便不再继续. 每次递归调用之后越来越接近这个限制条件. 二.递归模板 void

  • C语言 递归解决青蛙跳台阶问题

    C语言 递归解决青蛙跳台阶问题

    目录 前言 一.求解思路 二.代码实现 1.参考代码 2.运行结果 总结 前言 一只青蛙一次可以跳1级或2级台阶,求当台阶数为n时青蛙有多少种跳法. 一.求解思路 台阶的数量为n. 当 n = 1 时,青蛙有一种跳法,即跳1级台阶. 当 n = 2 时,青蛙有两种跳法,即跳两次1级台阶或跳一次2级台阶. 当 n = 3 时,青蛙可以先跳2级台阶再跳1级台阶,也可以选择先跳1级台阶再跳2级台阶,或者是跳三次1级台阶.依次类推,我们就能知道台阶数为n时青蛙的跳法. 但是,这样子是不是很麻烦呢,再仔细

  • C语言递归系列的深入总结

    C语言递归系列的深入总结

    递归 什么是递归 递归简而言之就是函数自己调用自己 如图所示 但是递归并不是简简单单的自己调用自己的过程 它分为 传递 和 回归,传递就是橙色箭头 回归则是黑色箭头 这就是递归 以 计算阶乘为例,假设我们输入6 计算6的阶乘为例 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> int factorial(int x) //递归体函数 { if (x == 1) { return 1; } return x * (factorial(x - 1

  • C语言学好递归看这一篇就够了

    C语言学好递归看这一篇就够了

    前言 在一定的时间.空间限制下,人的体力有限,思维力也有限,递归思维对实践最有用的指导,就是把脑力集中于定义问题这个关键点上,不用去找解题的过程.定义(问题)即解决(问题),定义即解决! 让大问题变成规模更小的问题并立即获得解决,以此作为基础,让我们轻松解决函数本身定义的问题.所以,递归在编程中同样是很重要的一个知识点. 提示:以下是本篇文章正文内容 一.递归是什么? 先来看一下定义: 程序调用自身的编程技巧称为递归( recursion). 简单来说,就是在一个函数里面调用函数自己本身. 举个

  • SpringBoot后端接口的实现(看这一篇就够了)

    摘要:本文演示如何构建起一个优秀的后端接口体系,体系构建好了自然就有了规范,同时再构建新的后端接口也会十分轻松. 一个后端接口大致分为四个部分组成:接口地址(url).接口请求方式(get.post等).请求数据(request).响应数据(response).如何构建这几个部分每个公司要求都不同,没有什么"一定是最好的"标准,但一个优秀的后端接口和一个糟糕的后端接口对比起来差异还是蛮大的,其中最重要的关键点就是看是否规范! 本文就一步一步演示如何构建起一个优秀的后端接口体系,体系构建

  • 程序员最实用的 SQL 语句收藏,看完这篇就够了

    程序员最实用的 SQL 语句收藏,看完这篇就够了

    前言 文章沿着设计一个假想的应用 awesome_app 为主线,从零创建修改数据库,表格,字段属性,索引,字符集,默认值,自增,增删改查,多表查询,内置函数等实用 SQL 语句.收藏此文,告别零散又低效地搜索经常使用的 SQL 语句.所有 SQL 都在 MySQL 下通过验证,可留着日后回顾参考,也可跟着动手一起做,如果未安装 MySQL 可参考 <macOS 安装 mysql> (windows 安装大同小异). 1. 创建 1.1 创建数据库 语法:create database db_

  • Java-lambda表达式入门看这一篇就够了

    Java-lambda表达式入门看这一篇就够了

    概述 Lambda表达式,也可称为闭包,是JDK8的新特性.Lambda 允许把函数作为一个方法的参数(函数作为参数传递进方法中),可以使代码变的更加简洁紧凑.Lambda表达式是一个可传递的代码块,可以在以后执行一次或多次. 名字起源是以前还没有计算机时,逻辑学家Alonzo Church想要形式化的表示能有效计算的数学函数,使用了希腊字母lambda( λ \lambda λ)来标记参数,从那以后,带参数变量的表达式就被称为lambda表达式. lambda表达式本质是一个匿名函数,比如以下

  • 关于Android多渠道打包问题看这一篇就够了

    关于Android多渠道打包问题看这一篇就够了

    目录 一.多渠道配置 二.注意事项 Android 多渠道打包看这一篇就够了 本文三个流程 一.多渠道配置 1.多渠道配置 2.不同渠道不同签名配置 3.不同渠道不同资源文件配置 4.不同渠道不同依赖配置 二.注意事项 三.打包 1.命令行打包 2.IDE 打包 多渠道配置(2 种方式) 1.可写在主模块(app)的 build.gradle 下 android { compileSdkVersion 29 buildToolsVersion "29.0.3" defaultConfi

  • C++内存管理看这一篇就够了

    C++内存管理看这一篇就够了

    目录 1 内存分布图 2 C语言和C++内存分配实现 2.1 C语言实现 2.2 C++实现 new的原理 delete的原理 3 C语言和C++内存管理区别 4 内存泄漏 总结 1 内存分布图 注意: 1.向下生长:地址由高到低 2.向上生长:地址由低到高 3.栈又叫堆栈,非静态局部变量/函数参数/返回值等等 4.堆用于程序运行时动态内存分配 2 C语言和C++内存分配实现 2.1 C语言实现 malloc函数 void *malloc(size_t size) 分配所需的内存空间,单位是字节

  • SpringBoot中并发定时任务的实现、动态定时任务的实现（看这一篇就够了）推荐

    一.在JAVA开发领域,目前可以通过以下几种方式进行定时任务 1.单机部署模式 Timer:jdk中自带的一个定时调度类,可以简单的实现按某一频度进行任务执行.提供的功能比较单一,无法实现复杂的调度任务. ScheduledExecutorService:也是jdk自带的一个基于线程池设计的定时任务类.其每个调度任务都会分配到线程池中的一个线程执行,所以其任务是并发执行的,互不影响. Spring Task:Spring提供的一个任务调度工具,支持注解和配置文件形式,支持Cron表达式,使用简单

  • Mybatis配置解析看这一篇就够了

    Mybatis配置解析看这一篇就够了

    目录 核心配置文件 environments元素 mappers元素 Mapper文件 Properties优化 typeAliases优化 生命周期和作用域 总结 核心配置文件 mybatis-config.xml 系统核心配置文件 MyBatis 的配置文件包含了会深深影响 MyBatis 行为的设置和属性信息. 能配置的内容如下: configuration(配置) properties(属性) settings(设置) typeAliases(类型别名) typeHandlers(类型处

  • Python eval() 函数看这一篇就够了

    目录 一.语法和参数 二.expression参数示例 三.globals参数示例 四.locals参数示例 五.eval函数的危险之处 六.eval()函数官方文档 附eval()函数常见作用有 总结 一.语法和参数 在Python中evel()函数的语法格式为eval(expression, globals=None, locals=None),注意后面还有globals参数和locals参数.eval()函数用于执行一个字符串表达式,并且返回该表达式的值.与eval相近的有exec函数,该

  • python操作Excel神器openpyxl看这一篇就够了

    目录 Excel xlsx Openpyxl 创建新文件 Openpyxl 写入单元格 Openpyxl 附加值 OpenPyXL 读取单元格 OpenPyXL 读取多个单元格 Openpyxl 按行迭代 Openpyxl 按列迭代 统计 Openpyxl 过滤器&排序数据 Openpyxl 维度 工作表 合并单元格 Openpyxl 冻结窗格 Openpyxl 公式 OpenPyXL 图像 Openpyxl 图表 总结 Excel xlsx 在本教程中,我们使用 xlsx 文件. xlsx 是

随机推荐