4

I'm having trouble wrapping my head around a way to use recursion to create a list and then returning that list for the base case. Specifically, I'm entering two 32 bit numbers (x1 and x2) into an ALU and evaluating them bit by bit (via ALU1) and then creating a list of the resulting number. My base case for this recursion algorithm is (null? x1) but at this point, how do I access the resulting list? I know lists in scheme are immutable, so I can't just create an empty list and append the resulting list to it. Any help? This is my first go at functional programming, so thanks in advance.

(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))))))
Improve this question

4 Answers 4

Reset to default
5

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 conses 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 performALU1`, an operation on the current elements of both lists, as you're traversing two lists simultaneously.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks, of course it would be so simple! For some reason, I didn't think the constructed list would still output if I were to output something like '() (I thought it would just output '().)
@Vance you're welcome! If this answer was helpful for you, please consider accepting it.
0

Probably you just want the empty list, written null. So:

(if (null? x1)
    null
    (cons ...))
Improve this answer

Comments

0

here is a way to create a new list of lists: Essentially opposite order.

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

Improve this answer

Comments

-1

Recursion - Here is a metaphor.

Imagine that you are moving house. You have a bunch of stuff that needs shifting and you need to ensure that it arrives in the new home.

Get a bunch of friends to fill the truck. They will have other friends that can help. hose people will have other friends etc. Until it boils down to one person sthifting a bit of your stuff into the truck.

Now each person has a bit of paper to tell you what is in the truck before the more. Now you have a list by ciollecting those bits of paper.

Improve this answer

1 Comment

Thanks, I understand the basics of recursion, I'm just new to scheme and am having trouble doing so in a functional programming way. My main problem is understanding how to access this new recursion-created-list without being able to name this list or append it to another list that I can access.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.