数据结构和算法学习二,之循环和递归
2023-09-14 08:59:07 时间
引自:http://blog.csdn.net/feixiaoxing/article/details/6838362
其实编程的朋友知道,不管学什么语言,循环和递归是两个必须学习的内容。当然,如果循环还好理解一点,那么递归却没有那么简单。我们曾经对递归讳莫如深,但是我想告诉大家的是,递归其实没有那么可怕。所谓的递归就是函数自己调用自己而已,循环本质上也是一种递归。
1)求和递归函数
我们可以举一个循环的例子,前面我们说过,如果编写一个1到n的求和函数怎么写呢,你可能会这么写:
int calculate(int m) { int count = 0; if(m <0) return -1; for(int index = 0; index <= m; index++) count += index; return count; }
上面只是一个示范。下面我们看看如果是递归应该怎么写呢?
int calculate(int m) { if(m == 0) return 0; else return calculate(m -1) + m; }
大家看着两段代码有什么不同?
(1)第一段代码从0,开始计算,从0到m逐步计算;第二段代码是从10开始计算,逐步到0之后这回,这样同样可以达到计算的效果
(2)第一段代码不需要重复的压栈操作,第二段需要重复的函数操作,当然这也是递归的本质
(3)第一段代码比较长,第二段代码较短
2)查找递归函数
大家可能说,这些代码有些特殊。如果是查找类的函数,有没有可能修改成递归函数呢?
int find(int array[], int length, int value) { int index = 0; if(NULL == array || 0 == length) return -1; for(; index < length; index++) { if(value == array[index]) return index; } return -1; }
大家可能说,这样的代码可能修改成这样的代码:
int _find(int index, int array[], int length, int value) { if(index == length) return -1; if(value == array[index]) return index; return _find(index + 1, array, length, value); } int find(int array[], int length, int value) { if(NULL == array || length == 0) return -1; return _find(0, array, length, value); }
3) 指针变量遍历
结构指针是我们喜欢的遍历结构,试想如果有下面定义的数据结构:
typedef struct _NODE { int data; struct _NODE* next; }NODE;
那么,此时我们需要对一个节点链接中的所有数据进行打印,应该怎么办呢?大家可以自己先想想,然后看看我们写的代码对不对。
void print(const NODE* pNode) { if(NULL == pNode) return; while(pNode){ printf("%d\n", pNode->data); pNode = pNode->next; } }
那么此时如果改成递归,那就更简单了:
void print(const NODE* pNode) { if(NULL == pNode) return; else printf("%d\n", pNode->data); print(pNode->next); }
其实,写这么多,就是想和大家分享一下我个人的观点:循环是一种特殊的递归,只有递归和堆栈是等价的。所有的递归代码都可以写成堆栈的形式,下面的一片博客我们就讨论一下堆栈和递归的关系。要想写好,必须熟练掌握堆栈。
【预告: 下面一片博客介绍堆栈和递归】
相关文章
- 原子循环计数器
- 循环,元组,字典,列表练习题
- Destoon7.0百度批量循环推送至百度
- Java实现有理数的循环节
- Python快速学习04:循环 & 函数
- 信息摘要算法-CRC(循环冗余校验)
- 数据结构与算法-9 高性能循环队列 Disruptor [MD]
- Python 入门(五)条件判断和循环
- Linux Shell脚本自动化编程实战- while、until循环
- Spring Bean 循环依赖为什么需要三级缓存
- 事件循环深度学习
- Atitit mybatis业务流程配置化管理总结 目录 1. Mybatis1 2. 流程模型常见的bpm模式1 2.1. 活动task 流程,getway流程控制(分支跳转 循环等)1 3
- easyExcel-复杂表头-多个流,多个sheet循环读取【分段读取】案例
- 【素数问题】整理几种计算素数的算法,包含:两层循环,开根号法,埃氏筛选法,欧拉筛选法
- Py之pandas:在表格文件中增加数据之for循环纵向/竖向非覆盖式增加数据到同一个csv文件内
- Algorithm:C++语言实现之字符串相关算法(字符串的循环左移、字符串的全排列、带有同个字符的全排列、串匹配问题的BF算法和KMP算法)
- 零基础学Python(第八章 for循环·超重点,本章会有几个简单的单层循环练习,后续会有针对算法的单独章节)
- 失去循环标签的Python,我这样实现跳出外层循环
- Python实现哈里斯鹰优化算法(HHO)优化循环神经网络回归模型(LSTM回归算法)项目实战
- Python实现GWO智能灰狼优化算法优化循环神经网络回归模型(LSTM回归算法)项目实战
- Python实现贝叶斯优化器(Bayes_opt)优化循环神经网络回归模型(LSTM回归算法)项目实战
- 2.3 循环队列
- 什么是循环神经网络模型?
- 循环队列
- go-008-循环语句
- C语言使用技巧(二十二):算法技巧:while(1)与if循环的循环扣圈搜索与路径节点搜索
- BFS (1)算法模板 看是否需要分层 (2)拓扑排序——检测编译时的循环依赖 制定有依赖关系的任务的执行顺序
- Bellman-Ford算法——为什么要循环n-1次?图有n个点,又不能有回路,所以最短路径最多n-1边。又因为每次循环,至少relax一边所以最多n-1次就行了!
- 算法工程师面试之循环神经网络RNN
- 【数据结构与算法】什么是双向循环链表?以及实现过程
- 【数据结构与算法】单向循环链表(增加元素、删除元素、打印循环链表等功能)
- 数据结构和算法 递归/循环遍历二叉树
- 【排序算法】图解直接插入排序(图解堪比Debug显示每次循环结果)