Recursion and Returning a list in Scheme

list, recursion, scheme

Solution

Assuming that both `x1` and `x2` have the exact same length, this should work:

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

When you're performing recursion on an input list, and building a new output list as a result, the base case is `if (null? lst)` then return the empty list `'()`. That's because the resulting list is being built at each step when you `cons` new elements; when you reach the last element of the input list, you've already built the output list and the only thing left to do is returning the end-of-list marker, `'()`.

To see it more clearly, try with a simpler example. This procedure simply copies the list received as input:

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

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

Notice that again the base case is `if (null? lst)` and the recursive step `cons`es the current element of the list `(car lst)` with the result of recurring on `(cdr lst), the rest of the list. In your case, you perform`ALU1`, an operation on the current elements of both lists, as you're traversing two lists simultaneously.

Problem

Original source