Haskell入门(四):递归(recursion)
参考教材:Learn You a Haskell for Great Good (http://learnyouahaskell.com/)
操作环境:Ubuntu下Linux64位虚拟机
python入门编程, 之后用c++学习数据结构,Haskell萌新。
因为对Haskell中少量词语的中文翻译并不理解,接下来的内容中重点名词将有英文和我了解的中文。
Chapter4主要内容
? ? ?递归这一章并没有特别强调函数式编程与面向对象编程的区别。事实上,递归更多地是一种思想。
? ? 递归基本原理
? ? ? ? 递归的主要想法是把一个大问题拆解为同类型的小问题。因为程序应该是有限的,我们要求它能在某种情景下结束运行。这种情景应当是确定的,已知的,不需要再拆解的。在编程中它被称为基础情景(base case)。
????????它与数学归纳法相似。我们需要先确定最基础的情况的结果可解,再确认可以由相对小的情景相对大的情景。在函数式编程里,可以了解为“将大定义用小定义处理”。
????????(题外:在这里推荐《算法引论》,尽管没有《算法导论》那么大名鼎鼎,但是这本书中对数学归纳法的了解还是很有启发性的)
? ? ? ? 斐波那契数列是典型的用递归定义的。我们来看看它的实现。
斐波那契数列
? ? ? ? 上面这一算法的时间效率并不好,不过我们在这里只是作为递归的例子。
????使用递归实现函数
? ? ? ? 在理解了递归的基本原理后,我们试着用递归实现少量基础功能。
????????求同类型列表的最大值(maximum)
????????????????假如列表长度为0, 抛出错误。假如列表只有一个元素,该元素即为最大值。否则,列表的最大值是列表head与tail部分最大值的较大值。具体实现如图。??
求同类型列表的最大值
????返回指定数目的某个元素重复构成的列表(take)
? ? ? ? ? ? 假如指定的数目不是正整数,则返回空列表。否则,返回的是重复次数减一情况下的列表,在开头加入该元素。
? ? ? ? ? ??
求同类型列表的最大值
? ? ? ? ? ? 中间报错的部分是因为在使用-时,它不能确定是负数还是减号。加入括号后问题得到处理。
? ? 取前几个元素
????????假如剩余列表为空,或者者剩余要取的不是正整数, 则返回空列表。否则,返回的是从tail部分取个数减一后的元素,并在开头剩余列表的head。(自己看着觉得很绕,可能看代码会好少量?)
取前几个元素
? ? 判断某个元素能否在列表中出现? ?(elem)?
? ? ? ? ? ? 假如列表为空,返回False.假如元素与列表的head相同,返回True。否则,判断元素能否在列表的tail部分出现。
判断某个元素能否在列表中出现
? ? 列表元组对应打包(zip)
? ? ? ? ? ? 假如某个列表为空,则返回空。否则,将两个列表的tail部分元组对应打包后,在开头加入由两个head组成的tuple。
列表元组对应打包
? ? ? ? ? ? 假如两个列表长度不等,则某一个先达到[], 且递归部分返回[], 因此返回列表长度以两个列表中短的为准。
? ? 快速排序(quick sort)
? ? ? ? ? ? 递归处理快排的想法是:假如列表为空列表或者者只有一个元素,那么它肯定是排序好了的。否则,我们先确定一个基准(方便起见,我们取首个元素为基准),将比它大的放在它右边,比它小的放在它左边。分别排序左右两边,当两边排序完毕时,整个列表就排序完毕了。
快速排序
? ? ? ? ????一个元素的情况也可以拆解为空列表的情况,因此第四行可以省略。
? ? ? ? ? ? 非递归处理快速排序可以参考百度百科中的代码。
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » Haskell入门(四):递归(recursion)