2 tail recursive functions for length [racket]

Question

I am trying to write two separate tail recursive functions that compute the length of a list and I am given these limitations:

1. write a version, lengtht that is tail recursive and uses external (non-nested) auxiliary functions as needed

2. write a second version, lengtht2 that uses no additional top-level functions. The function should still be tail-recursive, and can use any local bindings that you want

I am new to racket and this is what I understand the general form of tail recursion is:

(define (func x)
    (cond (end-test-1 end-value-1)
          (end-test-2 end-value-2)
          (else (func reduced-x))))

I am just a little confused about how to do this

Answer 1

Essentially, a tail recursive function keeps calling itself until it reaches its end condition. Unlike "regular" recursion, however, it passes intermediate answers to itself until it reaches the end.

An example would be this:

(define (find-length i lst)
  (if
    (null? lst) i
    (find-length (+ i 1) (cdr lst))))

The function takes two values: i, which tracks the length of the list so far, and lst, the list we're counting the elements of. i, for all intents and purposes, is our running count of the elements in the list. So if we call this method, we'll want to call it with i initialized to 0.

First we check that the list is not empty. (null?) If the list is empty, we can assume that we've counted all the elements, so we simply return i, which is our running count. This is our end condition.

Otherwise, we call find-length again. This time, however, we've incremented i by one and dropped the first element from the list (cdr lst).

For example, let's say we call the function like this:

(find-length 0 (list 2 3 4 3 5 3))

As we evaluate, the program would recursively call:

(find-length 1 '(3 4 3 5 3))
(find-length 2 '(4 3 5 3))
(find-length 3 '(3 5 3))
(find-length 4 '(5 3))
(find-length 5 '(3))
(find-length 6 '()) ; end condition, return 6

This question is a good reference for tail recursion in general.

Answer 2

This looks like homework, so I'll give you some hints to point you in the right direction, and you can fill-in the blanks. Try this for the first question:

(define (loop lst acc)              ; receives a list and an accumulator
  (cond ((null? lst) <???>)         ; if the list is empty return the accumulator
        (else (loop <???> <???>)))) ; advance the recursion, +1 to accumulator

(define (length1 lst)
  (loop <???> <???>))               ; how should we initialize the iteration?

Try this for the second question:

(define (length2 lst)
  (letrec ((loop <???>)) ; lambda with the same procedure as the previous `loop`
    (loop <???> <???>))) ; start the recursion exactly the same as in `length1`

In any case, think for a moment: what's the length of an empty (null) list? the answer will show you how to initialize the iteration. And for both solutions, we use an extra parameter called acc for keeping track of the answer so far, and we pass it along with the list to a looping tail-recursive procedure.