How is it possible that a function can call itself

Question

I know about recursion, but I don't know how it's possible. I'll use the fallowing example to further explain my question.

(def (pow (x, y))
     (cond ((y = 0) 1))
           (x * (pow (x , y-1))))

The program above is in the Lisp language. I'm not sure if the syntax is correct since I came up with it in my head, but it will do. In the program, I am defining the function pow, and in pow it calls itself. I don't understand how it's able to do this. From what I know the computer has to completely analyze a function before it can be defined. If this is the case, then the computer should give an undefined message when I use pow because I used it before it was defined. The principle I'm describing is the one at play when you use an x in x = x + 1, when x was not defined previously.

Answer 1

Compilers are much smarter than you think. A compiler can turn the recursive call in this definition:

(defun pow (x y)
  (cond ((zerop y) 1)
        (t (* x (pow x (1- y))))))

into a goto intruction to re-start the function from scratch:

Disassembly of function POW
(CONST 0) = 1
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
12 byte-code instructions:
0     L0
0     (LOAD&PUSH 1)
1     (CALLS2&JMPIF 172 L15)              ; ZEROP
4     (LOAD&PUSH 2)
5     (LOAD&PUSH 3)
6     (LOAD&DEC&PUSH 3)
8     (JSR&PUSH L0)
10    (CALLSR 2 57)                       ; *
13    (SKIP&RET 3)
15    L15
15    (CONST 0)                           ; 1
16    (SKIP&RET 3)

If this were a more complicated recursive function that a compiler cannot unroll into a loop, it would merely call the function again.