了解Haskell中的递归 [英] Understanding recursion in Haskell
问题描述
我很难理解如何以递归的方式思考问题，并使用Haskell解决问题.我花了数小时的阅读试图绕过递归.我最经常从理解它的人那里得到的解释是不清楚的，就像您传递一个函数，将该函数的名称作为参数，然后该函数将执行，解决一小部分问题并调用该函数.一次又一次地起作用，直到您击中基本情况为止."
I am having a very difficult time understand how to think about problems in a recursive way, and solve them using Haskell. I have spent hours of reading trying to wrap my head around recursion. The explanation I most often get from people who understand it is never clear and is something like "you pass a function, the name of the function as the argument, the function will then execute, solving a small piece of a the problem and calling the function again and again until you hit the base case".
请问有人足够友善，并引导我完成这三个简单的递归函数的思考过程吗?不是它们的功能，而是代码如何最终递归地执行和解决问题.
Can someone please be kind enough, and walk me through the thought process of these three simple recursive functions? Not so much the functionality of them, but how the code, ends up executing and solving the problem, recursively.
非常感谢！
功能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]
推荐答案
指南
尝试理解递归时，您可能会发现更容易思考算法对于给定输入的行为.容易迷上执行路径的样子，所以反而问自己以下问题:
Guidelines
When trying to understand recursion, you may find it easier to think about how the algorithm behaves for a given input. It's easy to get hung up on what the execution path looks like, so instead ask yourself questions like:
- 如果我传递一个空列表会怎样?
- 如果我传递包含一个项目的列表会怎样?
- 如果我传递包含很多物品的列表会怎样?
或者，对于数字的递归:
Or, for recursion on numbers:
- 如果我传递一个负数会怎样?
- 如果我传递0会怎样?
- 如果我传递的数字大于0会怎样?
递归算法的结构通常只是覆盖以上情况的问题.因此，让我们看看您的算法如何表现出对这种方法的感觉:
The structure of a recursive algorithm is often just a matter of covering the above cases. So let's see how your algorithms behave to get a feel for this approach:
maximum [] = error
maximum [1] = 1
maximum [1, 2] = 2
如您所见，唯一有趣的行为是#3.其他人只是确保算法终止.查看定义，
As you can see, the only interesting behaviour is #3. The others just ensure the algorithm terminates. Looking at the definition,
maximum' (x:rest) = max x (maximum' rest)
用[1, 2]调用会扩展为:
maximum [1, 2] ~ max 1 (maximum' [2])
~ max 1 2
maximum'通过返回一个数字来工作，这种情况下，该数字知道如何使用max进行递归处理.让我们再看一种情况:
maximum' works by returning a number, which this case knows how to process recursively using max. Let's look at one more case:
maximum [0, 1, 2] ~ max 0 (maximum' [1, 2])
~ max 0 (max 1 2)
~ max 0 2
对于此输入，您可以看到第一行中对maximum'的递归调用与上一个示例完全相同.
You can see how, for this input, the recursive call to maximum' in the first line is exactly the same as the previous example.
reverse [] = []
reverse [1] = [1]
reverse [1, 2] = [2, 1]
反向通过将给定列表的开头粘贴在末尾来进行.对于空列表，这不涉及任何工作，因此这是基本情况.因此，给出定义:
Reverse works by taking the head of the given list and sticking it at the end. For an empty list, this involves no work, so that's the base case. So given the definition:
reverse' (x:xs) = reverse' xs ++ [x]
让我们做些替代.鉴于[x]等同于x:[]，您可以看到实际上有两个值需要处理:
Let's do some substitution. Given that [x] is equivalent to x:[], you can see there are actually two values to deal with:
reverse' [1] ~ reverse' [] ++ 1
~ [] ++ 1
~ [1]
足够容易.对于两个元素的列表:
Easy enough. And for a two-element list:
reverse' [0, 1] ~ reverse' [1] ++ 0
~ [] ++ [1] ++ 0
~ [1, 0]
take'
此函数引入了对整数参数和列表的递归，因此有两种基本情况.
take'
This function introduces recursion over an integer argument as well as lists, so there are two base cases.
-
如果我们带零个或更少的物品会怎样?我们不需要带任何物品，所以只需返回空白列表即可.
What happens if we take 0-or-less items? We don't need to take any items, so just return the empty list.
take' n _ | n <= 0 = []
take' -1 [1] = []
take' 0 [1] = []
如果我们传递一个空列表会怎样?没有更多可取的项目，因此请停止递归.
What happens if we pass an empty list? There are no more items to take, so stop the recursion.
take' _ [] = []
take' 1 [] = []
take -1 [] = []
算法的实质实际上是沿着列表走，将输入列表拉开，并减少要采取的项目数量，直到上述两种基本情况中的任何一个都停止了该过程.
The meat of the algorithm is really about walking down the list, pulling apart the input list and decrementing the number of items to take until either of the above base cases stop the process.
take' n (x:xs) = x : take' (n-1) xs
因此，在首先满足数字基数的情况下，我们在到达列表末尾之前就停止了.
So, in the case where the numeric base case is satisfied first, we stop before getting to the end of the list.
take' 1 [9, 8] ~ 9 : take (1-1) [8]
~ 9 : take 0 [8]
~ 9 : []
~ [9]
在首先满足列表基本情况的情况下，我们在计数器达到0之前用完了所有项目，只是返回了我们可以得到的结果.
In the case where the list base case is satisfied first, we run out of items before the counter reaches 0, and just return what we can.
take' 3 [9, 8] ~ 9 : take (3-1) [8]
~ 9 : take 2 [8]
~ 9 : 8 : take 1 []
~ 9 : 8 : []
~ [9, 8]
这篇关于了解Haskell中的递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
