Non-tail recursive function that returns the last element in list without using reverse?

Question

Im trying to make a non-tail recursive function returns the last element of a list without using reverse, map, iteration, mutation of any sort (built in or user-built). So far I have successfully made a tail-recursive version and a non-tail version that uses reverse func. But I just cannot figure how to make a non-tail recursive function.

I really appreciate your help!

Answer 1

Imagine you have the tail recursive version like this:

(define (last-element lst)
  (if base-case-expression
      result-expression
      recursion-expression))

Now in order to not make it tail recursive you just make your function do something with the result. eg. cache it in a binding and then return:

(define (last-element lst)
  (if base-case-expression
      result-expression
      (let ((result recursion-expression))
        result)))

Here the recursive call is not the tail position. However a sufficiently smart compiler might make compiled code that is tail recursive. Eg. a lot of Scheme implementations transform code to continuation passing style and then every call becomes a tail call and stack is replaced with growing closures. The result of that on both versions will be very similar.

Answer 2

Note: for some reason I wrote this answer using Common Lisp, before noticing that the question was tagged with scheme, racket, and lisp. In any case, Common Lisp falls under the latter tag, and the code is easily adapted to either Scheme or Racket.

For a function to be non-tail recursive, you need to place recursive calls so that they are not in tail position, i.e., so that no further operations are needed on the results of the recursive call before it is returned. So, you need a recursive strategy for getting to the last element of a list that does further operations on the result of recursive calls.

One strategy would be to build a "reversed list" on the way back up from the base case, taking that list apart at the same time so that the desired result is left at the end. Here is a reversal function to show the idea without taking anything apart:

(defun reversal (xs)
  (if (cdr xs)
      (cons (reversal (cdr xs)) (car xs))
      xs))

The above function builds a nested dotted list with the elements of the input list in reverse:

CL-USER> (reversal '(1 2 3 4 5))
(((((5) . 4) . 3) . 2) . 1)

Now, the car function could be called numerous times on this result to get the last element of the input, but we can just do this as the new list is constructed:

(defun my-last (xs)
  (car (if (cdr xs)
           (cons (my-last (cdr xs)) (car xs))
           xs)))

Here the my-last function is called after calling (trace my-last):

CL-USER> (trace my-last)
(MY-LAST)
CL-USER> (my-last '(1 2 3 4 5))
  0: (MY-LAST (1 2 3 4 5))
    1: (MY-LAST (2 3 4 5))
      2: (MY-LAST (3 4 5))
        3: (MY-LAST (4 5))
          4: (MY-LAST (5))
          4: MY-LAST returned 5
        3: MY-LAST returned 5
      2: MY-LAST returned 5
    1: MY-LAST returned 5
  0: MY-LAST returned 5
5

This solution requires two operations on the result of calling my-last, i.e., cons and car. It does seem possible that an optimizer could notice that car is being called on the result of a cons, and optimize my-last to something like:

(defun my-last-optimized (xs)
  (if (cdr xs)
      (my-last-optimized (cdr xs))
      (car xs)))

If this were the case, then the optimized code would be tail recursive, and tail call optimizations could then be applied. I do not know if any lisp implementations can do this sort of optimization.

An alternate strategy would be to store the original list and then to take it apart on the way back up from the base case using cdr. Here is a solution using a helper function:

(defun my-last-2 (xs)
  (car (my-last-helper xs xs)))

(defun my-last-helper (xs enchilada)
  (if (cdr xs)
      (cdr (my-last-helper (cdr xs) enchilada))
      enchilada))

This also works as expected. Here is an example, again using trace to see the function calls. This time both my-last-2 and my-last-helper have been traced:

(trace my-last-2 my-last-helper)
(MY-LAST-2 MY-LAST-HELPER)
CL-USER> (my-last-2 '(1 2 3 4 5))
  0: (MY-LAST-2 (1 2 3 4 5))
    1: (MY-LAST-HELPER (1 2 3 4 5) (1 2 3 4 5))
      2: (MY-LAST-HELPER (2 3 4 5) (1 2 3 4 5))
        3: (MY-LAST-HELPER (3 4 5) (1 2 3 4 5))
          4: (MY-LAST-HELPER (4 5) (1 2 3 4 5))
            5: (MY-LAST-HELPER (5) (1 2 3 4 5))
            5: MY-LAST-HELPER returned (1 2 3 4 5)
          4: MY-LAST-HELPER returned (2 3 4 5)
        3: MY-LAST-HELPER returned (3 4 5)
      2: MY-LAST-HELPER returned (4 5)
    1: MY-LAST-HELPER returned (5)
  0: MY-LAST-2 returned 5
5

In this case, the only operation required after recursive calls to my-last-2 return is cdr, but that is enough to prevent this from being a tail call.