Just call that recursive function something else. Give it some other name, and say that we must take it for granted that this other name is a function which is already debugged and tested by another team of programmers:

   (defun our-member (item list)
     (cond
       ((atom list) nil)
       ((eql item (car list)) list)
       (t (member item (cdr list)))))

We first convince ourselves that what we have works.

And then, final step: since what we have works, it means that our-member is a correct implementation of member, which means that the two are equivalent. Equivalent functions are substitutable. And so we can just perform that substitution: replace the member call with our-member.

By the way, it occurs to me that Hofstadter's Gödel, Escher and Bach might be a good source of ideas on how to deal with presenting and teaching self-referential topics.

That seems like it's "begging the question" --- as in, "if there's already a function written to do what I want, why do I need it to write one to do it...?"

Someone already wrote a Celsius to Fahrenheit conversion function, a simple ray-tracer, a quicksort, a toy Lisp, a text-file-based simple inventory system, etc ...

We could make up a back story about this to give it real-world plausibility: yes, the function is already written, but it's in an expensive, proprietary third-party library which we cannot ship without paying royalty fees and being bogged down with various inconvenient restrictions.

   (defun our-member (item list)
     (cond
       (t (member item list))))

so step 1:

   (defun our-member (item list)
     (cond
       ((atom list) nil)     ;; if it's not a non-empty list, it can't be a list containing item
       (t (member item (cdr list)))))

   (defun our-member (item list)
     (cond
       ((atom list) nil)            ;; if it's not a non-empty list, it can't be a list containing item
       ((eql (car list) item) list) ;; if the first element of the list is our item,
                                    ;; we have a match and return the whole list
       (t (member item list))))

   (defun our-member (item list)
     (cond
       ((atom list) nil)              ;; if it's not a non-empty list, it can't be a list containing item
       ((eql (car list) item) list)   ;; if the first element of the list is our item,
                                      ;; we have a match and return the whole list
       (t (member item (cdr list))))) ;; we already know that the first item is not a match, so we can just run
                                      ;; member on the tail of the list

[edit]

derp (atom nil) => T

I've sometimes got past the "leap of faith" step by replacing the recursive call with a call to a built-in. e.g.

  >>> sum([1, 2, 3, 4]) == 10
  True
  >>> def my_sum(xs):
  ...   if xs == []: return 0
  ...   else: return xs[0] + sum(xs[1:])
  >>> my_sum([1, 2, 3, 4]) == 10

Edit: It appears I've written an identical comment to my sibling.

...which is why you should always teach recursion by starting with the base case and build on it with a recursive call, not the other way around. Step through an example execution of the algorithm with no recursive calls --- only the base case. Then step through with one or two levels of recursive calls, and they'll usually start seeing the pattern of how it works (and be able to generalise to n levels.)

I think the way to teach recursion to programmers who have mastered iteration is to teach the tricks for transforming loops into tail recursion: start by equating the self reference with the establishment of new values for the loop variables and the backward branch.

E.g. given a working dot product:

    double dot(double *a, double *b, size_t n)
    {
       double acc = 0;
       while (n-- != 0)
         acc += *a++ + *b++;
       return acc;
    }

    #define dot_rec(label, na, nb, nn, nacc) { \
      /* capture argument evaluations into fresh temporary variables */ \
      double *tna = (na), *tnb = (nb); \
      size_t tnn = (nn); \
      double tnacc = (nacc); \
      /* store temporaries to loop variables, and jump backward */ \
      a = tna; b = tnb; n = tnn; acc = tnacc; \
      goto label; \
    }
 
    double dot(double *a, double *b, size_t n)
    {
       double acc = 0.0;
    again:
       if (n != 0)  /* we can now use (n > 0) since n isn't decremented! */ 
         dot_rec(again, a + 1, b + 1, n - 1, acc + *a * *b);
       return acc;
    }

The dot_rec macro ensures that the expression * a is not affected by a receiving a + 1; it mimics the binding of argument expression values to fresh arguments.

From that we can go to recursion:

    double dot_rec(double *a, double *b, size_t n, double acc)
    {
       if (n > 0)
         return dot_rec(again, a + 1, b + 1, n - 1, acc + *a * *b);
       return acc;
    }

    double dot(double *a, double *b, size_t n)
    {
       return dot_rec(a, b, n, 0.0);
    }

Then go into non-tail recursion; recursion in which the parent actually does something with the return value other than just return it: those true divide-and-conquer problems.

Then mutual recursion among two or more functions, starting with something trivial like odd(n) and even(n) that mutually tail recurse.

    double dot(double *a, double *b, size_t n)
    {
       double acc = 0;
       while (n-- != 0)
         acc += *a++ + *b++;
       return acc;
    }

         acc += *a++ + *b++;

         acc += *a++ * *b++;

Oh well, s/dot product/"dot sum"/ :) :) :)

> how your recursive version does it

See, everyone? Recursion irons out bugs!