我很难理解如何以递归方式思考问题，并使用 Haskell 解决它们。我花了几个小时阅读试图围绕递归来解决问题。我最常从理解它的人那里得到的解释永远不清楚，就像“你传递一个函数，函数的名称作为参数，然后函数将执行，解决一小部分问题并调用一次又一次地发挥作用，直到你达到基本情况”。
有人可以请足够好心，并引导我完成这三个简单递归函数的思考过程吗？与其说是它们的功能，不如说是代码如何递归地执行和解决问题。
提前谢谢了！
功能一
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:rest) = max x(maximum' rest)
功能二
take' n _
| n <= 0 = []
take' _ [] = []
take' n (x:xs) = x : take' (n-1) xs
功能 3
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
在尝试理解递归时，您可能会发现更容易思考算法对于给定输入的行为方式。很容易对执行路径的样子感到困惑，所以问自己以下问题：
或者，对于数字的递归：
递归算法的结构通常只是覆盖上述情况。因此，让我们看看您的算法如何表现以了解这种方法：
maximum [] = error
maximum [1] = 1
maximum [1, 2] = 2
如您所见，唯一有趣的行为是#3。其他人只是确保算法终止。看定义，
maximum' (x:rest) = max x (maximum' rest)
调用它[1, 2]扩展为：
maximum [1, 2] ~ max 1 (maximum' [2])
~ max 1 2
maximum'通过返回一个数字来工作，这种情况下知道如何使用max. 我们再看一个案例：
maximum [0, 1, 2] ~ max 0 (maximum' [1, 2])
~ max 0 (max 1 2)
~ max 0 2
您可以看到，对于此输入，maximum'第一行中的递归调用与前面的示例完全相同。
reverse [] = []
reverse [1] = [1]
reverse [1, 2] = [2, 1]
反向工作通过获取给定列表的头部并将其粘贴在末尾。对于一个空列表，这不涉及任何工作，所以这是基本情况。所以给出定义：
reverse' (x:xs) = reverse' xs ++ [x]
让我们做一些替换。鉴于这[x]相当于x:[]，您可以看到实际上有两个值需要处理：
reverse' [1] ~ reverse' [] ++ 1
~ [] ++ 1
~ [1]
很容易。对于两元素列表：
reverse' [0, 1] ~ reverse' [1] ++ 0
~ [] ++ [1] ++ 0
~ [1, 0]
此函数引入了对整数参数和列表的递归，因此有两种基本情况。
如果我们取 0 或更少的物品会发生什么？我们不需要拿任何物品，所以只返回空列表。
take' n _ | n <= 0 = []
take' -1 [1] = []
take' 0 [1] = []
如果我们传递一个空列表会发生什么？没有更多的项目可以采取，所以停止递归。
take' _ [] = []
take' 1 [] = []
take -1 [] = []
该算法的核心实际上是遍历列表，拉开输入列表并减少要获取的项目数量，直到上述任一基本情况停止该过程。
take' n (x:xs) = x : take' (n-1) xs
因此，在首先满足数字基本情况的情况下，我们在到达列表末尾之前停止。
take' 1 [9, 8] ~ 9 : take (1-1) [8]
~ 9 : take 0 [8]
~ 9 : []
~ [9]
在首先满足列表基本情况的情况下，我们会在计数器达到 0 之前用完项目，然后返回我们能做的。
take' 3 [9, 8] ~ 9 : take (3-1) [8]
~ 9 : take 2 [8]
~ 9 : 8 : take 1 []
~ 9 : 8 : []
~ [9, 8]
递归是将某个函数应用于集合的一种策略。您将该函数应用于该集合的第一个元素，然后对其余元素重复该过程。
举个例子，您想将列表中的所有整数加倍。首先，您考虑我应该使用哪个功能？答案 -> 2*，现在你必须递归地应用这个函数。让我们称之为它apply_rec，所以你有：
apply_rec (x:xs) = (2*x)
但是这只改变了第一个元素，你想改变集合上的所有元素。因此，您还必须将 应用于apply_rec其余元素。因此：
apply_rec (x:xs) = (2*x) : (apply_rec xs)
现在你有一个不同的问题。什么时候apply_rec结束？当您到达列表末尾时，它就结束了。换句话说[]，因此您也需要涵盖这种情况。
apply_rec [] = []
apply_rec (x:xs) = (2*x) : (apply_rec xs)
当您到达终点时，您不想应用任何功能，因此该功能apply_rec应该“返回” []。
让我们看看这个函数在 set = 中的行为[1,2,3]。
apply_rec [1,2,3] = (2 * 1) : (apply_rec [2,3])apply_rec [2,3] = 2 : ((2 * 2) : (apply_rec [3]))apply_rec [3] = 2 : (4 : ((2 * 3) : (apply_rec []))apply_rec [] = 2 : (4 : (6 : [])))导致[2,4,6].
由于您可能不太了解递归，因此最好从比您提供的示例更简单的示例开始。还可以看看学习递归和这个Haskell 教程 3-递归。
您问的是“思维过程”，大概是程序员，而不是计算机，对吗？所以这是我的两分钱：
考虑g使用递归编写一些函数的方法是，假设您已经编写了该函数。就这样。
这意味着您可以在需要时使用它，并且它“会做”它应该做的任何事情。所以只要写下那是什么——制定它必须遵守的法律，写下你所知道的一切。说点什么吧。
现在，只是说g x = g x不是说什么。当然这是真的，但它是一个毫无意义的重言式。如果我们说它g x = g (x+2)不再是同义反复，但无论如何都是没有意义的。我们需要说一些更明智的话。例如，
g :: Integer -> Bool
g x | x<=0 = False
g 1 = True
g 2 = True
在这里我们说点什么。还，
g x = x == y+z where
y = head [y | y<-[x-1,x-2..], g y] -- biggest y<x that g y
z = head [z | z<-[y-1,y-2..], g z] -- biggest z<y that g z
我们是否已经说出了我们不得不说的一切x？无论我们做了还是没有，我们都说过任何 x可能的事情。这就是我们的递归定义——一旦所有的可能性都用尽了，我们就完成了。
但是终止呢？我们想从我们的函数中得到一些结果，我们希望它完成它的工作。这意味着，当我们使用它来计算 时x，我们需要确保我们以递归方式使用它，其中一些是“之前”y定义的，即“更接近”我们拥有的最简单定义的案例之一。 x
在这里，我们做到了。现在我们可以惊叹于我们的手艺，
filter g [0..]
最后一件事是，为了理解一个定义，不要试图追溯它的步骤。只需阅读方程式本身。如果我们看到上面的定义g，我们会简单地把它理解为：g是一个布尔函数，它是一个数字，它True代表 1 和 2，以及任何x > 2它前面两个g数字的和。
看功能3：
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
假设你调用了 reverse' [1,2,3] 然后......
1. reverse' [1,2,3] = reverse' [2,3] ++ [1]
reverse' [2,3] = reverse' [3] ++ [2] ... so replacing in equation 1, we get:
2. reverse' [1,2,3] = reverse' [3] ++ [2] ++ [1]
reverse' [3] = [3] and there is no xs ...
** UPDATE ** There *is* an xs! The xs of [3] is [], the empty list.
We can confirm that in GHCi like this:
Prelude> let (x:xs) = [3]
Prelude> xs
[]
So, actually, reverse' [3] = reverse' [] ++ [3]
Replacing in equation 2, we get:
3. reverse' [1,2,3] = reverse' [] ++ [3] ++ [2] ++ [1]
Which brings us to the base case: reverse' [] = []
Replacing in equation 3, we get:
4. reverse' [1,2,3] = [] ++ [3] ++ [2] ++ [1], which collapses to:
5. reverse' [1,2,3] = [3,2,1], which, hopefully, is what you intended!
也许你可以尝试对其他两个做类似的事情。选择小参数。
取得成功！
也许您提出问题的方式不是很好，我的意思是这不是通过研究现有递归函数的实现，您将了解如何复制它。我更愿意为您提供一种替代方式，它可以被视为一个有条不紊的过程，可以帮助您编写递归调用的标准框架，然后促进对它们的推理。
您所有的示例都是关于列表的，那么使用列表时的第一件事就是详尽无遗，我的意思是使用模式匹配。
rec_fun [] = -- something here, surely the base case
rec_fun (x:xs) = -- another thing here, surely the general case
现在，基本情况不能包含递归，否则你肯定会以无限循环结束，那么基本情况应该返回一个值，掌握这个值的最好方法是查看函数的类型注释。
例如 ：
reverse :: [a] -> [a]
可以鼓励您将基本情况视为 [a] 类型的值，将 [] 视为反向
maximum :: [a] -> a
可以鼓励您将基本情况视为 a 类型的最大值
现在对于递归部分，如上所述，该函数应该包括对她自己的调用。
rec_fun (x:xs) = fun x rec_fun xs
用 fun 表示使用另一个函数负责实现递归调用的链接。为了帮助您的直觉，我们可以将其呈现为操作员。
rec_fun (x:xs) = x `fun` rec_fun xs
现在考虑（再次）您的函数的类型注释（或更简单地说是基本情况），您应该能够推断出此运算符的性质。对于反向，因为它应该返回一个列表，所以运算符肯定是连接（++）等等。
如果你把所有这些东西放在一起，最终得到所需的实现应该不难。
当然，与任何其他算法一样，您总是需要稍微思考一下，并且没有神奇的秘诀，您必须思考。例如，当您知道列表尾部的最大值时，列表的最大值是多少？
我也一直发现很难递归思考。浏览http://learnyouahaskell.com/递归章节几次，然后尝试重新实现他的重新实现有助于巩固它。此外，一般来说，通过仔细阅读Mostly Adequate Guide并练习柯里化和组合来学习功能性编程使我专注于解决问题的核心，然后以其他方式应用它。
回到递归......基本上这些是我在考虑递归解决方案时经历的步骤：
因此，例如，如果您必须反转列表，则基本情况将是一个空列表或一个元素的列表。转到递归情况时，不要考虑[1,2,3,4]. 而是考虑最简单的情况 ( [1,2]) 以及如何解决该问题。答案很简单：取尾巴并附加头部以获得相反的效果。
我不是haskell专家......我刚开始学习自己。我从这个有效的开始。
reverse' l
| lenL == 1 || lenL == 0 = l
where lenL = length l
reverse' xs ++ [x]
守卫检查它是长度为 1 还是 0 的列表，如果是则返回原始列表。
当列表的长度不是 0 或 1 并获得尾部的反转，附加头部时，就会发生递归情况。这种情况会一直发生，直到列表长度为 1 或 0 并且您得到答案。
然后我意识到你不需要检查单例列表，因为一个元素列表的尾部是一个空列表，我去了这个，这是 learnyouahaskell 中的答案：
reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]
我希望这会有所帮助。归根结底，熟能生巧，所以继续尝试递归地解决一些问题，你就会得到它。