理解递归(haskell)的求值

Question

我有以下代码：

foo x y z
| null x = y
| null z = y
| otherwise = foo (tail x) ([head x] ++ y ++ [head z]) (tail z)

和以下输入：

1. [1] [2] [3]
2. [1,3,4] [2] [3,4]
3. [1,0] [2] [3,4]

情况1的评估：

otherwise: foo [] [1,2,3] []
null x = [1,2,3]
null z = [1,2,3]

输出：[1，2，3]

案例2的评估：

otherwise: foo [3,4] [1,2,3] [4]
foo [4] [3,2,4] []
null z = [3,2,4]

输出：[3,1,2,3,4]

案例3评估：

otherwise: foo [0] [1,2,3] [4]
foo [] [0,2,4] []
null x = [0,2,4]
null z = [0,2,4]

输出：[0,1,2,3,4]

我不明白在最后一步之后递归是如何组成的

Answer 1

关于您问题中的代码，可能存在拼写错误：在情况2中，x或z都不是null，因此您在编写时使用otherwise，但这意味着您在[2,3]上调用foo，而不是[3,4]，以及[1,2,3]和[4]。请复习你的问题。

转到您的，我不明白在最后一步之后递归是如何组成的，事情很简单：您的函数是从x和z中截取元素(同时，就像在同一级别的递归中一样(，只要每个元素上都有一个或多个，同时使y增长。然后，一旦x或z(或两者(变为null，您将通过返回y退出递归。