Recursion is when a definition or procedure refers to a smaller or simpler instance of itself.

A recursive algorithm needs two conceptual pieces:

• a base case that can be solved directly;
• a recursive step that reduces the problem toward the base case.

For factorial,

In ordinary function recursion, each unfinished call usually occupies a stack frame containing local state and where execution should return. That makes recursion elegant for trees, divide-and-conquer algorithms, and inductive structures, but very deep recursion can overflow a language/runtime's call stack.

Recursion and iteration are often computationally equivalent ways to express a process. A recursive formulation is not automatically faster, more mathematical, or more intelligent.

The concept becomes stranger with self-reference: a system can encode statements or structures that indirectly describe themselves. That is one reason recursion connects naturally to Gödel, Escher, Bach — but ordinary recursive programming and Gödelian self-reference are not the same phenomenon.