理解Haskell中的递归

Question

我很难理解如何以递归方式思考问题,并使用Haskell解决它们.我花了几个小时阅读试图绕过递归.我经常从理解它的人那里得到的解释从来都不清楚,就像"你传递一个函数,函数的名称作为参数,函数将执行,解决一小部分问题并调用一次又一次地起作用,直到你击中基础案例".

有人可以请你好心,并引导我完成这三个简单的递归函数的思考过程吗？与其说是功能不是很多,而是代码如何以递归方式执行并解决问题.

提前谢谢了!

功能1

maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:rest) = max x(maximum' rest)

功能2

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]

采取'

此函数引入了整数参数和列表的递归,因此有两种基本情况.

1. 如果我们采取0或更少的项目会发生什么？我们不需要任何物品,所以只需返回空列表即可.

   take' n _   | n <= 0    = [] 
   
   take' -1 [1]  = []
   take' 0  [1]  = []
   

2. 如果我们传递一个空列表会怎么样？没有更多的项目,所以停止递归.

   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]