Rewriting a common function using tail-end recursion

user_10453278 0
Viewed 55

I've been trying to tinker with this code to rewrite a "repeat" function using tail-end recursion but have gotten a bit stuck in my attempts.

(define (repeat n x)
  (if (= n 0)
      '()
      (cons x (repeat (- n 1) x))))

This is the original "repeat" function. It traverses through 'n - 1' levels of recursion then appends 'x' into a list in 'n' additional recursive calls. Instead of that, the recursive call should be made and the 'x' should be appended to a list at the same time.

(define (repeat-tco n x)
  (trace-let rec ([i 0]
                  [acc '()])
    (if (= i n)
        acc
        (rec (+ i 1) (cons x acc)))))

This is the closest rewritten version that I've come up with which I believe follows tail-call recursion but I'm not completely sure.

racket tail-recursion recursion lisp
1 Answers

Your repeat-tco function is indeed tail recursive: it is so because the recursive call to rec is in 'tail position': at the point where it's called, the function that is calling it has nothing left to do but return the value of that call.

[The following is just some perhaps useful things: the answer is above, but an answer which was essentially 'yes' seemed too short.]

This trick of taking a procedure p which accumulates some result via, say (cons ... (p ...)) and turning it into a procedure with an extra 'accumulator' argument which is then tail recursive is very common. A result of using this technique is that the results come out backwards: this doesn't matter for you because all the elements of your list are the same, but imagine this:

(define (evens/backwards l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))

This will return the even elements of its arguments, but backwards. If you want them the right way around, a terrible answer is

(define (evens/terrible l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        es
        (loop (rest lt)
              (if (even? (first lt))
                  (append es (list (first lt)))
                  es)))))

(Why is it a terrible answer?) The proper answer is

(define (evens l)
  (let loop ([lt l]
             [es '()])
    (if (null? lt)
        (reverse es)
        (loop (rest lt)
              (if (even? (first lt))
                  (cons (first lt) es)
                  es)))))
user_170269340
Related