haskell - 理解 Haskell 中的递归

Question

我很难理解如何以递归方式思考问题，并使用 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]  

Answer 1

指导方针

在尝试理解递归时，您可能会发现更容易考虑算法对于给定输入的行为方式。很容易对执行路径的样子感到困惑，所以问自己以下问题:

如果我传递一个空列表会发生什么？

如果我通过一个包含一个项目的列表会发生什么？

如果我传递一个包含许多项目的列表会发生什么？

或者，对于数字的递归:

如果我传递一个负数会发生什么？

如果我通过 0 会发生什么？

如果我传递一个大于 0 的数字会怎样？

递归算法的结构通常只是覆盖上述情况。因此，让我们看看您的算法如何表现以了解这种方法:

最大'

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]