0

我正在阅读Simply Scheme，然后进入递归部分。

我不明白为什么当满足基本情况时，Scheme 返回递归过程的“构建”值，而不是导致基本情况评估为的实际参数值#t。

例如，看一下递归过程的示例代码片段，该过程将单词作为输入，将其反转，然后将其吐出：

(define (reverse wd)
  (if (empty? wd) wd
      (word (last wd) (reverse (bl wd)))))

这让我感到困惑：(if (empty? wd) wd

我知道当形式参数的实际参数值为wd空（或""）时，基本情况的计算结果为#t，导致第二个参数的值if被计算。

我不if明白的是( ，在这种情况下)的第二个参数如何wd返回非空的东西，即使它看起来是触发基本情况的相同的、空的、正式的参数。

我错过了什么？

如果文档（或文本）中有某些内容可以解释这一点，我很乐意对其进行审查。

4

2 回答 2

2

由于状态在这里没有改变，你可以用它的递归替换函数所做的事情。想象一下，你有一个两个字母的单词a：

(reverse a) ; =>
(word (last a) (reverse (bl a))) ; ==>
(word (last a) (word (last (bl a)) (reverse (bl (bl a))))) ; ==>
(word (last a) (word (last (bl a)) (bl (bl a)))) ; ==>
(word (last a) (word (last (bl a)) '()))

最后一个(bl (bl a))是最后一次迭代所做的唯一事情，它是'(). 其余的作为先前调用的延续完成。

编辑

澄清..想象a是“ab”

(reverse "ab") ; turns into
(word (last "ab") (reverse (bl "ab")))           ; tuns into
(word "b" (reverse (bl "ab")))                   ; turns into 
(word "b" (reverse "a")))                        ; turns into 
(word "b" (word (last "a") (reverse (bl "a"))))) ; turns into
(word "b" (word "a" (reverse ""))))

现在看看最后一个。当(reverse "")返回 "" 时，它是前一个表单调用中使用的结果，在word表单中，所以你会得到(word "a" "") ==> "a"，然后将返回到第一个调用(word "b" "a"). 这些是延续。

于 2014-02-06T10:02:42.537 回答
1

关键的见解是它对于基本情况返回空。那是因为空字符串的反转是空字符串。

递归案例实际上是在这个假设下工作的。简而言之，这是您的reverse功能的工作方式：

  1. 如果给定单词​​为空，则返回空。
  2. 否则，从单词中取出最后一个字母，并将其与单词其余部分的反面连接起来。

例子。假设我们正在反转“Devin”：

  • “Devin”这个词不是空的，所以我们将“n”与“Devi”的反面连接起来。
    • “Devi”这个词不是空的，所以我们将“i”与“Dev”的反面连接起来。
      • “Dev”这个词不是空的，所以我们将“v”与“De”的反义词连接起来。
        • “De”这个词不是空的，所以我们将“e”和“D”的反义词连接起来。
          • “D”这个词不是空的，所以我们将“D”与“”的反面连接起来。
            • “”这个词是空的，所以我们返回“”。
          • 在这里，我们返回“D”与“”连接，即“D”。
        • 在这里，我们返回“e”和“D”，即“eD”。
      • 在这里，我们返回与“eD”连接的“v”，即“veD”。
    • 在这里，我们返回与“veD”连接的“i”，即“iveD”。
  • 在这里，我们返回与“iveD”连接的“n”，即“niveD”。
于 2014-02-06T11:45:45.380 回答