4

我很难找到一种使用递归创建列表然后返回该列表作为基本情况的方法。具体来说，我将两个 32 位数字（x1 和 x2）输入 ALU 并逐位评估它们（通过 ALU1），然后创建结果数字的列表。我对这个递归算法的基本情况是 (null?x​​1) 但此时，我如何访问结果列表？我知道方案中的列表是不可变的，所以我不能只创建一个空列表并将结果列表附加到它。有什么帮助吗？这是我第一次接触函数式编程，所以提前致谢。

(define ALU-helper 
   (lambda (selection sub x1 x2 carry-in n)
      (if (null? x1)
          (________?)
          (cons
              (ALU1 selection sub (car x1) (car x2) carry-in n) 
              (ALU-helper selection sub (cdr x1) (cdr x2) carry-in (- n 1))))))
4

4 回答 4

5

假设两者x1和x2具有完全相同的长度，这应该有效：

(define ALU-helper 
  (lambda (selection sub x1 x2 carry-in n)
    (if (null? x1)
        '()
        (cons
         (ALU1 selection sub (car x1) (car x2) carry-in n) 
         (ALU-helper selection sub (cdr x1) (cdr x2) carry-in (- n 1))))))

当您对输入列表执行递归并因此构建新的输出列表时，基本情况if (null? lst)将返回空列表'()。那是因为当你cons添加新元素时，每一步都会生成结果列表；当您到达输入列表的最后一个元素时，您已经构建了输出列表，剩下要做的就是返回列表结束标记，'().

为了更清楚地看到它，请尝试使用更简单的示例。此过程只是复制作为输入接收到的列表：

(define (copy lst)
  (if (null? lst)
      '()
      (cons (car lst)
            (copy (cdr lst)))))

(copy '(1 2 3 4 5))
> (1 2 3 4 5)

请注意，基本情况是if (null? lst)，递归步骤cons是列表的当前元素，(car lst)其结果是在(cdr lst), the rest of the list. In your case, you performALU1 上重复执行，这是对两个列表的当前元素的操作，因为您同时遍历两个列表。

于 2012-04-08T14:48:26.913 回答
0

可能你只想要空列表，写成null. 所以：

(if (null? x1)
    null
    (cons ...))
于 2012-04-08T13:40:56.180 回答
0

这是一种创建新列表列表的方法： 基本上相反的顺序。

(define envers (lambda (lat) (cond ((null?lat) '()) (else (list (envers (cdr lat)) (car lat) )) ) )

于 2015-05-27T02:44:03.133 回答
-1

递归 - 这是一个隐喻。

想象一下，你正在搬家。你有一堆东西需要转移，你需要确保它到达新家。

找一群朋友来装满卡车。他们会有其他可以提供帮助的朋友。软管人会有其他朋友等。直到归结为一个人将您的一些东西转移到卡车上。

现在每个人都有一张纸告诉你之前卡车里有什么。现在你有一个通过收集这些纸片的清单。

于 2012-04-08T08:43:18.970 回答