haskell趣学指南学习笔记4:你好,递归

你好,递归

本章我们好好审视了递归,并体会了为何递归在haskell中有着如此的重要性

借助递归的方法,学习了寻找简洁而优雅的求解方法

递归

  • 递归是指在函数的定义中应用自身的方式
  • 按照递归的思想,一般倾向于将问题展开为同样的子问题,并不断的对问题进行展开和求解,直到抵达问题的基准条件(base case)为止,基准条件中,问题不必做分解,而由程序员明确的给出一个非递归的结果

递归与haskell

递归在haskell中至关重要:
– 在haskell中,重要的不是给出求解的步骤,而是定义问题与解的描述

4.1 不可思议的最大值

下面我们用maximum函数举一个例子.以下是maximum函数的一种递归的实现

4.2 更多的几个递归函数的实现

4.2.1 replicate

replicate函数取一个整数和一个元素作为参数,返回一个包含多个重复元素的列表

4.2.2 take

4.2.3 reverse

4.2.4 repeat

这个例子虽然没有显式的基准条件,但由于haskell是惰性的,只要使用take能够在某位置截断他即可

4.2.5 zip

4.2.6 elem

4.3 快点,排序

取一组可比较的元素构成的列表,并对其进行求解,这一问题天生就适合使用递归进行解决

接下来使用快速排序作为例子

4.3.1 算法思路

  • 取得一个待排序的列表,取得它的第一个元素,找出列表中所有比5小的元素安排到5的左侧,大的安排到右侧,在这里这个作为比较标准的元素被称为基准(pivot)
  • 然后对基准的左侧和右侧分别递归地调用同一个函数

4.3.2 编写代码

4.4 递归的思考

递归的固定模式

  • 先定义基准条件,也就是应对特殊输入的简单非递归解
  • 然后将问题分解为一个或多个子问题,并递归的调用自身
  • 最后基于子问题里得到的结果,组合成为最终解
Tagged with:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据