# ## 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
maximum [1, 2] = 2
``````

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' )
~ 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
``````

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     = 
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]
``````

Let's do some substitution. Given that `[x]` is equivalent to `x:[]`, you can see there are actually two values to deal with:

``````reverse'     ~ reverse' [] ++ 1
~ []          ++ 1
~ 
``````

Easy enough. And for a two-element list:

``````reverse' [0, 1] ~ reverse'  ++ 0
~ [] ++  ++ 0
~ [1, 0]
``````

## take'

This function introduces recursion over an integer argument as well as lists, so there are two base cases.

1. 如果我们带零个或更少的物品会怎样?我们不需要带任何物品，所以只需返回空白列表即可.

1. 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   = []
take' 0    = []
``````

• 如果我们传递一个空列表会怎样?没有更多可取的项目，因此请停止递归.

• 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) 
~ 9 : take 0     
~ 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) 
~ 9 : take 2     
~ 9 : 8 : take 1 []
~ 9 : 8 : []
~ [9, 8]
``````