Racket language Accumulator tail recursive

Question

I am trying to write a tail-recursive function with an accumulator of joining two sorted lists. input: (40 43 50)(42 46 48) output: (40 42 43 46 48 50)

It needs to be done tail-recursive where we call the accumulator to another function. I am getting stuck in what needs to go in the accumulator function.

(define (rec l1 l2 acc))

   (rec (rest l1) l2)

(define (foo l1 l2)
  (cond
    ((null? l1) l2)
    ((null? l2) l1)
    (else
       (cond
         ((<= (car l1) (car l2)) (rec (l2 (cons (first l1) (acc))))

                
         ((> (car l1) (car l2)) (rec (l1 (cons (first l2) (acc))))

               
                           ))))))

Answer 1

You are consing to l1 or l2 and even call the lists as functions, which will not work. In reality you need to cons to the accumulator argument. Here is an example of reverse using tail recursive and accumulator:

(define (reverse lst)
  (reverse-helper lst '()))

(define (reverse-helper lst acc)
  (if (null? lst)
      acc ; acc already in reverse
      (reverse-helper (cdr lst) (cons (car lst) acc))))

You can also keep the helper local:

(define (reverse lst)
  (define (helper lst acc)
    (if (null? lst)
        acc ; acc already in reverse
        (helper (cdr lst) (cons (car lst) acc))))
  (helper lst '()))

Your version would need more cases. Eg. base case when l1 and l2 are empty. Two cases where either l1 or l2 are empty, and then the last case you cons the lowest of the first element of l1 and l2 and cdr that one for next.. Thus you'll see something like this this if you trace or add breakpoint in the beginning of it:

(merge-helper '(1 3 5 6 7) '(2 3 4) '()) ; ==> 
(merge-helper '(3 5) '(2 3 4) '(1)) ; ==> 
(merge-helper '(3 5) '(3 4) '(2 1)) ; ==> 
(merge-helper '(5) '(3 4) '(3 2 1)) ; ==> 
(merge-helper '(5) '(4) '(3 3 2 1)) ; ==> 
(merge-helper '(5 6 7) '() '(4 3 3 2 1)) ; ==> 
(merge-helper '() '() '(7 6 5 4 3 3 2 1)) ; ==> 
(reverse '(7 6 5 4 3 3 2 1)) ; ==> 
(1 2 3 3 4 5 6 7)

Good luck

Answer 2

You could also use optional arguments to have it in one function:

(define (merge l1 l2 (acc '()) )
  (cond ((and (null? l1) (null? l2)) (reverse acc))
        ((null? l1) (merge '() (cdr l2) (cons (car l2) acc)))
        ((null? l2) (merge (cdr l1) '() (cons (car l1) acc)))
        ((test (car l1) (car l2)) (merge (cdr l1) l2 (cons (car l1) acc)))
        (else (merge l1 (cdr l2) (cons (car l2) acc)))))

If you want to deal with lists consisting not necessarily of numbers, you have introduce a smaller-test which you can then change at will:

(define (merge l1 l2 (smaller-test <) (acc '()) )
  (cond ((and (null? l1) (null? l2)) (reverse acc))
        ((null? l1) (merge '() (cdr l2) smaller-test (cons (car l2) acc)))
        ((null? l2) (merge (cdr l1) '() smaller-test (cons (car l1) acc)))
        ((smaller-test (car l1) (car l2)) (merge (cdr l1) l2 smaller-test (cons (car l1) acc)))
        (else (merge l1 (cdr l2) smaller-test (cons (car l2) acc)))))

Then you can also do:

(merge '("a" "c" "f") '("b" "d" "f") string<=?)
;; => '("a" "b" "c" "d" "f" "f")