I was having trouble getting lisp's trace function to show any useful information so I talked to the professor. If you're compiling and then executing your lisp files like I was, the compiler can optimize out tail-recursion. So when you trace a recursive function, it looks like it only gets called once.
The solution is to load your lisp file using lisp's load function, like this:
It won't get compiled. Now you can trace your recursive function:
And then when you call it, you'll see the traced output. Hope that helps someone.