Recursion

Any program written in recursive style can also be written using a loop and a stack. (A stack is a type of data structure usually studied in a second course in computer science.) Each recursive call is replaced with a push onto the stack, and each return from a recursive call is replaced with a pop of the stack.

Another way to think about this is that the recursive program is translated into the machine language of the processor, and so cannot have any more algorithmic power than that processor, which cannot have any more power than Turing complete.

Of course, writing a program that manipulates a stack is tedious and error prone. Recursion adds convenience and expressiveness to a language. With some languages, recursion is the preferred way to write programs, and using iteration is awkward and inconvenient. Lisp, Prolog, and Haskell work this way. These languages are usually used for research and problem solving rather than the productivity programs that C and Java are used for.