Running time and stack depth of a lisp recurrence
The time and other resources (such as stack consumption) needed to run an with the argument $x \in \mathbb{N}^*$ is the sum of:


the resources needed to compute (- k 1) with k bound to $x$;
the resources needed to compute an with the argument $x-1$;
the resources needed to compute (if (= k 0) alpha (+ (* beta $y$`) kappa))` where $y$ is the value returned by the recursive call to an.


Let $T(x)$ be the running time of this computation. For $x \gt 0$, by the analysis above, $T(x) = T(x-1) + C$ for some constant $C$ (assuming that the arithmetic operations take constant time). A very simple induction shows that $T(x) = C \, x + T(0)$, i.e. $T(x) = \Theta(x)$. The same goes for stack consumption.

There is more than one stack push per recursive call, (3 in a naive interpreted Lisp such as Emacs Lisp), but that doesn't affect the $O$ or $\Theta$ analysis. Other than this minor detail your analysis is correct.

Are you sure that you typed the right code? Emacs has a fairly low limit on stack usage but even it can sustain more recursive calls (up to 123 in Emacs 23 where max-lisp-eval-depth is 500).