CODEWITHSUNDEEP
listrecursionscheme
Vance
Vance

Reputation: 481

Recursion and Returning a list in Scheme

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

Upvotes: 4

Views: 11525

Answers (4)

Furry Owl
Furry Owl

Reputation: 1

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

Upvotes: 0

Óscar López
Óscar López

Reputation: 236004

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.

Upvotes: 5

Sam Tobin-Hochstadt
Sam Tobin-Hochstadt

Reputation: 5053

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

(if (null? x1)
    null
    (cons ...))

Upvotes: 0

Ed Heal
Ed Heal

Reputation: 60007

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.

Upvotes: -1

Related Questions