Recursion in computer science is a method of problem solving where the solution to a problem depends on solutions to smaller instances of the same problem.

Recursion is a kind of function call in which a function calls itself. Such functions are also called recursive functions.

Some functional programming languages do not define any looping constructs, but rely solely on recursion to repeatedly call code. Likewise, in languages that do provide loops, it is possible for any recursive function to be written using loops without requiring recursion.

This defines two basic approaches to repeatedly call some piece of code.

  • Iterative approach (Using loop constructs)
  • Recursive approach (Using recursion)

In addition to program code, recursion can also occur

  • in data structures, where a nested object or array may contain a reference to an element further up the data tree.
  • in mathematics, where recursion is used to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science.
history | excerpt history