recursion - 这个 Racket 程序是如何使用 add1 的？

Question

我试图了解如何在此递归示例中使用 add1:

(define (my-length a-list)
  (if (empty? a-list)
      0
      (add1(my-length (rest a-list)))))

如果给定 (my-list '(1 2 3 4)) 程序将返回数字 4。

我知道在函数 my-lenght 的每次迭代之后，代码都会拆开列表，直到列表为空。我不明白的是 (add1) 是如何将每次迭代添加到函数中的。

Answer 1

为了另一种解释:

从这里开始

(my-length '(a b c d))

通过将参数填充到函数中，变成

(if (empty? '(a b c d))
  0
  (add1 (my-length (rest '(a b c d)))))

显然，'(a b c d) 不是空的。因此评估 if 的“else”情况:

(add1 (my-length (rest '(a b c d))))
(add1 (my-length '(b c d)))

现在，(my-length '(b c d)) 是什么意思？好吧，如果我们将函数体复制粘贴到最后一行，我们会得到:

(add1 (if (empty? '(b c d))
        0
        (add1 (my-length (rest '(b c d))))))

继续...

(add1 (add1 (my-length (rest '(b c d)))))
(add1 (add1 (my-length '(c d))))

这一直持续到我们得到一个空列表:

(add1 (add1 (add1 (add1 (if (empty? '())
                              0
                              (add1 (my-length (rest '()))))))))

'() 为空，因此 if 语句返回 0:

(add1 (add1 (add1 (add1 0))))
(add1 (add1 (add1 1)))
(add1 (add1 2))
(add1 3)
4

这就像我们越来越深入地研究函数，因为对于我们采取的每一步，我们都需要再走一步来实际评估我们拥有的东西。

---

这与 (add1 '(a b c d)) 有何不同？您可以从评估结果中看出 add1 从未真正应用于 a、b、c 或 d。我们甚至从未检查过列表中的内容。您可以有一个包含四个列表的列表，每个列表都包含列表的列表，并且它会评估所有相同的列表。

具体来说，说 (add1 '(a b c d)) 就像在说“1 加草莓是多少？”，而您的函数更像是:

“这个列表里有多少东西？”

“好吧，如果您在顶部 ((first my-list)) 上没有看到任何东西，那么肯定没有。”

“好吧，好吧……我在上面看到一个“a”!”

“很好!把它拿出来。列表中至少有 1 个。”

“好的，但剩下的有多少？”

“我们再试一次怎么样？继续从列表顶部取出项目，直到列表为空。然后，我们将把它放回去，边走边数。”

“好的，我已经把它们都取出来了。我现在要把它们放回去:d，那是 1；c，那是 2；b，那是 3；a，那是 4!”

“好了，列表中有 4 个!”