Haskell多重递归,相互递归(合并排序Merge Sort)

Haskell多重递归,相互递归(合并排序Merge Sort)

多重递归Multiple recursion
本质上，当您在函数体中多次调用函数本身时，就会发生多次递归。
例子:
even :: Int -> Bool
even 0 = True
even n = odd (n-1)
odd :: Int -> Bool
odd 0 = False
odd n = even (n-1)

相互递归Mutual recursion
真的没什么特别的,只需要考虑n个基本情况和n（其中n是相互递归的程度）

优雅的排序
函数式编程（连同排序）可以为许多问题带来优雅的解决方案。
在 Java/C/Python/etc 中可能需要 10 行代码的事情通常可以在 Haskell 中用几行简洁易懂的行来表达。

合并排序Merge Sort
基本算法：将列表分成两半,对每一半进行排序,将两个排序列表合并在一起

将列表分成两半

将两个排序列表合并在一起

快速排序：提醒
划分：
选择一些称为枢轴(pivot)的元素。将其移动到排序序列中的最终位置，使所有较小的元素都在其左侧，较大的元素在其右侧。
征服：
对较小和较大元素的子数组进行递归排序
结合：
这里不需要做任何工作——在递归之后对数组进行排序。

一个不同的例子
我们查看了一个示例，在该示例中，字符串中的一个字符被另一个字符替换。更有用的是一个函数，其中一个子字符串被另一个子字符串替换。

生成一个质数列表
从 2 生成所有数字的列表,测试每个数字，看看它是否是质数
如果不是，请扔掉它;如果有，请保留

或者…

那么递归是一切的答案吗？不
这是一个非常强大的工具。但有时存在基于库函数的更优雅（和更有效）的解决方案
递归本质上是低效的,但有时在函数式编程中不可避免
函数式编程编译器非常复杂,编程语言中更高级别的抽象意味着编译器会做更多的工作,有一些技术允许编译器删除递归