递归并返回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是列表的当前元素,其(car lst)结果是在(cdr lst), the rest of the list. In your case, you performALU1` 上重复,这是对两个列表的当前元素的操作,因为您同时遍历两个列表.