Common Lisp中trace递归回溯阶段输出的作用解析

Let's start by restating your function clearly for reference:

(defun uniq (lst &optional ulst)
  (if (endp lst)
      ulst
      (if (member (car lst) ulst)
          (uniq (cdr lst) ulst)
          (uniq (cdr lst) (append ulst (list (car lst)))))))

Great question—this confusion is super common when first wrapping your head around recursive call stacks! Let's break down why that "backtracking" (more accurately, stack unwinding) happens even after the final result is built.

Here's the core idea: #

Recursive functions in Common Lisp (and most languages) use a call stack to track every ongoing function invocation. Each time you call uniq, a new stack frame is created that holds:

• The current values of lst and ulst
• The address to return to once this invocation finishes

When you hit the base case ((endp lst) is true), you return the final ulst (your deduplicated list). But this return value doesn't jump straight back to the original caller—it has to work its way up the stack, because every previous invocation of uniq is still waiting for its own recursive call to finish and return a value.

Let's walk through a tiny example to see this in action #

Suppose we call (uniq '(a b a)):

1. Invocation 1: lst = '(a b a), ulst = nil → a isn't in nil, so call (uniq '(b a) '(a))
2. Invocation 2: lst = '(b a), ulst = '(a) → b isn't in '(a), so call (uniq '(a) '(a b))
3. Invocation 3: lst = '(a), ulst = '(a b) → a is in '(a b), so call (uniq '() '(a b))
4. Invocation 4 (Base Case): lst = '(), so return '(a b)

Now comes the "backtracking" part:

• Invocation 3 receives the return value '(a b) and immediately returns it to Invocation 2
• Invocation 2 receives '(a b) and returns it to Invocation 1
• Invocation 1 receives '(a b) and returns it to you, the original caller

Each step of the stack unwinding is just passing the final result up to the level that asked for it. None of these steps modify the result—they're just completing the pending function calls that were waiting for the recursive chain to resolve.

Why does this matter? #

Even though the final ulst is built by the time we hit the base case, the original function call (Invocation 1) doesn't have access to that value directly. The call stack ensures that every nested invocation passes its result back up until the top-level call can return it to you.

As a side note: Your uniq function is actually tail-recursive (the recursive call is the last thing each branch does). Many Common Lisp implementations optimize tail recursion to reuse stack frames, which would make the "backtracking" steps invisible (since there's no stack to unwind). But if your trace shows the unwinding, it means either your implementation isn't optimizing tail recursion, or the trace tool is showing all logical invocations regardless of optimizations.

内容的提问来源于stack exchange，提问作者inspiron