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 回答