Recursion

Recursion refers to something being a part of its own definition.

 Description 
Usually, a recursive function refers to itself in some cases (or inputs), but not in every case. A function that referred to itself in every case would never terminate.

When a function refers to itself, it often uses a smaller input than the input it was given. In this way, it can solve a problem by first solving a simpler version of the problem.

 Example 
An example of a recursive function  is:

If  then return .
If  then return .
This function computes the factorial of a natural number. It works because  and .

The definition has two cases: a recursive case for , and a case for  that is not recursive. The case that is not recursive is called a "base case".

 Uses 

Recursion can be used to write computer programs. A program that uses recursion may be easier to write and understand than a program that does the same thing without recursion.

Recursion is used in mathematics to prove theorems. This method is called induction.

The idea of recursion can be seen in art and language. For example:
 A fractal image contains smaller versions of itself.
 In the rules of grammar, a sentence can be part of another sentence.

 Easter Eggs 
In the Google search engine, if you type up "recursion", it will say "Did you mean: Recursion", a reference to the meaning of recursion.

References

Category:Computer science