简单方案 Lisp 中的子集/子序列递归过程

Question

我正在结合伯克利的2011年夏季CS3课程完成Simply Scheme。我正在为理解子集/子序列过程而苦苦挣扎。一旦我看到解决方案代码，我就理解了基本的机制，但是我正在努力掌握足够的概念来自己提出解决方案。

有人能给我指出一个方向，帮助我更好地理解它吗？或者也许他们自己会有不同的解释？

这是我目前所理解的基础：

因此，在下面的过程中，作为< code>prepend参数的< code>subsequences递归调用将< code>word分解为其最基本的元素，而< code>prepend将< code>word的< code>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)))) 

因此，当输入（子序列“单词”）时，将返回第一个：

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

当输入< code >(子序列'(1 2 3))时，第二个将返回:

    ((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

递归是一种工具，可以帮助我们，使编程更容易。

递归方法不会试图一次解决整个问题。它说，如果我们已经有了解决方案代码呢？然后我们可以将其应用于原始问题的任何类似的较小部分，并收回解决方案。然后我们所要做的就是重新组合包含较小自相似部分的剩余“外壳”，以及该较小部分的结果；这样我们就可以得到完整问题的完整解决方案！

因此，如果我们能够识别数据中的递归结构；如果我们能像俄罗斯的“matryoshka”娃娃一样把它拆开，它的外壳里有自己的小复制品（里面也有自己的更小复制品，一直到最后），然后可以把它放回去；然后，我们需要做的就是变换整个“娃娃”中包含的嵌套“matryoshka”娃娃（所有嵌套娃娃都在里面——我们不在乎有多深！）通过应用我们试图创建的递归过程，并简单地返回结果：

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

等式两边的两个s是不同的，因为转换后的娃娃可能根本不是娃娃！（还有，

这是函数中使用的递归方案。

有些问题更适合其他递归方案，例如，各种排序，Voronoi图等最好通过分而治之来完成：

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

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

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

Answer 2

您的替代解决方案大多是好的，但是您在首次实现此（列表的幂集）功能时犯了与许多人相同的错误：您的基本情况是错误的。

有多少种方法可以从 0 元素列表中选择 0 个或多个项目的子集？“0”可能感觉很明显，但实际上有一种方法：不选择任何项目。因此，与其返回空列表（意思是“没有办法完成”），不如返回（list '（））（意思是，“一种方法的列表，即选择没有元素”）。等效地，您可以返回'（（））]，这与（list '（）相同 - 我不知道好的方案风格，所以我会把它留给你。

一旦您做出了更改，您的解决方案就会起作用，这表明您确实理解递归！

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