list - Scheme中的递归和返回列表

Question

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

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

Answer 1

假设两者 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 es 列表的当前元素 (car lst)结果在 (cdr lst), the rest of the list. In your case, you perform 上反复出现ALU1`，对两个列表的当前元素的操作，因为您同时遍历两个列表。