Simply Scheme Lisp 中的子集/子序列递归过程

Question

我正在结合伯克利的 2011 年夏季 CS3 课程学习 Simply Scheme。我正在努力理解 subset / subsequence 程序。看到解决方案代码后，我了解了基本机制，但我很难掌握足够的概念来自己提出解决方案。

谁能给我指明方向，帮助我更好地理解它？或者他们自己有不同的解释？

这是我目前理解的基础：

因此，在下面的过程中，作为 prepend 参数的 subsequences 递归调用正在将 word 分解为其最基本的元素，并且 prepend 将 word 的 first 添加到每个元素中。

; using words and sentences

(define (subsequences wd)
  (if (empty? wd)
      (se "")
      (se (subsequences (bf wd))
          (prepend (first wd) 
                   (subsequences (bf wd))))))

(define (prepend l wd)
  (every (lambda (w) (word l w))
         wd))

; using lists

(define (subsequences ls)
  (if (null? ls)
      (list '())
      (let ((next (subsequences (cdr ls))))
        (append (map (lambda (x) (cons (car ls) x))
                     next)
                next))))

所以第一个，当输入 (subsequences 'word) 时，会 return:

    ("" d r rd o od or ord w wd wr wrd wo wod wor word)

第二个，当输入(subsequences '(1 2 3))时，会return:

    ((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())

所以，正如我所说，这段代码有效。我分别了解代码的每个部分，并且在大多数情况下了解它们如何相互协作。嵌套的递归调用给我带来了麻烦。我只是不太了解它，无法自己编写此类代码。任何可能帮助我理解它的东西都将不胜感激。我想我只是需要一个新的视角来思考它。

提前感谢任何愿意为我指出正确方向的人。

编辑：

所以第一条评论让我试着解释一下我目前所理解的内容。开始了：

对于单词/句子过程，我认为它通过出现在第二位的递归调用将变量分解为它的“基本”情况（可以这么说）。

然后它基本上建立在最基本的情况下，通过前置。

我真的不明白为什么首先出现的递归调用需要在那里。

在列表一中，当我自己写的时候，我得到了这个：

(define (subseq lst)
  (if (null? lst)
      '()
      (append (subseq (cdr lst))
              (prepend (car lst)
                       (subseq (cdr lst))))))

(define (prepend i lst)
  (map (lambda (itm) (cons i itm)) 
       lst))

在我看来，如果使用正确的解决方案，列表中的 car 就会消失而不被考虑在内，但显然情况并非如此。我不明白这两个递归调用是如何协同工作的。

Answer 1

您的替代解决方案大部分都很好，但是您犯了很多人在第一次实现此（power-set 列表）功能时犯的同样错误：您的基本情况是错误的。

有多少种方法可以从 0 元素列表中选择 0 项或更多项的子集？ “0”可能感觉很明显，但实际上有一种方法：选择 none 项。因此，您应该 return (list '())（意思是 "a list of one way to do it, which is to choose no elements"），而不是 return 空列表（意思是 "there are no ways it can be done"）。等效地，你可以 return '(())，这与 (list '()) 相同 - 我不知道好的 Scheme 风格，所以我会把它留给你。

一旦您进行了更改，您的解决方案就会起作用，证明您毕竟确实理解了递归！

至于解释提供给您的解决方案，我不太明白您认为列表的 car 会发生什么。它实际上与您自己编写的算法几乎完全相同：要查看它有多接近，请内联您对 prepend 的定义（即，将其主体替换为您的 subsequences 函数）。然后从提供的解决方案中扩展 let 绑定，在它出现的两个地方替换它的主体。最后，如果你愿意，你可以将参数的顺序交换为 append - 或者不是；没关系。此时，它与您编写的功能相同。

Answer 2

Recursion 是一个工具，可以帮助我们，使编程更容易。

递归方法不会尝试一次解决整个问题。它说，如果我们已经有了解决方案代码怎么办？然后我们可以将它应用到原始问题的任何类似 smaller 部分，并得到 it 的解决方案。那么我们所要做的就是 re-combine 剩下的 "shell" 其中包含 smaller self-similar部分，较小部分的结果；这样我们就可以得到完整问题的完整解决方案！

所以如果我们可以识别我们数据中的那个递归结构；如果我们可以把它拆开，就像一个Russian "matryoshka" doll，在它的[=88=里面包含它自己的更小的副本 ]（它自身内部也包含较小的 self 副本，一直向下）并且可以 将其放回去 ；那么我们需要做的就是转换整个 "doll" 是转换其中包含的 nested "matryoshka" 玩偶（所有嵌套玩偶都在里面 - 我们不不关心有多少层深！）通过将我们正在寻求创建的递归过程应用于它，然后简单地放回结果:

    solution( shell <+> core )   ==   shell  {+}  solution( core )
;;            --------------                                ----

等式两边的两个+是不同的，因为变形后的人偶可能根本就不是人偶！（另外，左边的 <+> 是解构给定的数据，而右边的 {+} 构造整体结果。)

这是您的函数中使用的 recursion scheme。

有些问题更适合其他递归方案，例如各种，Voronoi图等最好用divide-and-conquer:

来完成

    solution( part1 <+> part2 )   ==   solution( part1 ) {+} solution( part2 )
;;            ---------------                    -----                 -----

至于两个 - 或一个 - 递归调用，因为这在数学上是一个函数，用相同的参数调用它的结果总是相同的。没有语义区别，只有操作区别。

有时我们更喜欢计算结果并将其保存在内存中以供进一步重用；有时我们更愿意在每次需要时重新计算它。就最终结果而言，这无关紧要——将计算相同的结果，唯一的区别是消耗的内存和/或产生该结果所需的时间。

Simply Scheme Lisp 中的子集/子序列递归过程

Subset / Subsequence Recursive Procedure in Simply Scheme Lisp

lisp

recursion

scheme

list

sequence

编辑：