Recursive calls overwrite argument values for caller

[8dcc]

When evaluating the following function:

(defun pre-recur (arg)
  (if (null? arg)
      "NULL-ARG"
      (list arg (pre-recur (cdr arg)))))

With the following function calls:

(pre-recur nil)       ; Result: "NULL-ARG"
(pre-recur '(a))      ; Result: ((a) "NULL-ARG")
(pre-recur '(a b))    ; Result: ((a b) ((b) "NULL-ARG"))
(pre-recur '(a b c))  ; Result: ((a b c) ((b c) ((c) "NULL-ARG")))

The results are correct; the arg symbol evaluates to the right value in each recursive call.

---

However, with the following function:

(defun post-recur (arg)
  (if (null? arg)
      "NULL-ARG"
      (list (post-recur (cdr arg)) arg)))

The same function calls:

(post-recur nil)       ; Result: "NULL-ARG"
(post-recur '(a))      ; Result: ("NULL-ARG" nil)
(post-recur '(a b))    ; Result: (("NULL-ARG" nil) nil)
(post-recur '(a b c))  ; Result: ((("NULL-ARG" nil) nil) nil)

Return invalid results. It seems that the arg symbol is getting overwritten with the value of the (chronologically) previous recursive calls.

It seems that the general evaluation process of (post-recur '(foo)) is:

1. Evaluate (cdr '(foo)) to nil.
2. Use that, nil, as the argument to the recursive call to post-recur.
   • In the recursive call, check if arg is null.
   • Since it is true, return "NULL-ARG".
3. The recursive call to post-recur returns "NULL-ARG", which will be used as the first argument of list.
4. The arg symbol is evaluated again from the first call to post-recur (not the recursive one), so it can be used as the second argument of list. It should evaluate to the original argument '(foo), but evaluates to nil, the value of arg in the recursive call.

Modifying post-recur confirms this theory.

(defun post-recur (arg)
  (if (equal? arg '(b))
      "GOT-B-ARG"
      (list (post-recur (cdr arg)) arg)))

(post-recur '(a b))    ; Result: ("GOT-B-ARG" (b))
(post-recur '(a a b))  ; Result: (("GOT-B-ARG" (b)) (b))

Once a recursive call is made, whenever arg is overwritten, the value also changes for the caller of that recursive call.