NFA recognizer in LISP

I have to define a function in lisp that, given a regular expression and an e-NFA as input, it returns true if the expression is accepted by the automata.

For start, I've defined a function that generates an e-NFA (as a cons-cell) from a regular expression with these operators {|, *, +, ...}.

For example: with the expression (or a b) the output will be:

((INITIAL 0) (DELTA 0 EPSILON 1) (DELTA 0 EPSILON 3) (DELTA 2 EPSILON 5) (DELTA 4 EPSILON 5) (DELTA 1 A 2) (DELTA 3 B 4) (FINAL 5))

I've come up with this idea: I've written the function recognize-or (which processes the or case):

(defun nfa-recognize-or (fa input init final)
 (let ((arc (cdr (car fa))))
  (cond ((and (equal (first arc) init) (equal (second arc) 'epsilon))
         (nfa-recognize-or (cdr fa) input (third arc) final))
        ((not (equal (first arc) init))
         (nfa-recognize-or (cdr fa) input init final))
        ((and (equal (first arc) init) (equal (second arc) (car input)))
         (nfa-recognize-or fa (cdr input) (third arc) final))
        ((equal (third arc) final)
         T)
  )
 )
)

If I call the function this way:

(nfa-recognize-or (cdr fa) '(a) 0 5)

It returns 'stack overflow'. The problem is that, after some calls, the value of fa =

(DELTA 1 A 2) (DELTA 3 B 4) (FINAL 5))

with init = 2 and final = 5 as before. At this point, the next state the program should consider should be

(DELTA 2 EPSILON 5)

in order to return TRUE, but this is not possible because at this point NFA is "consumed" and I can't backtrack it to verify the other states.

Do you have any suggestions?