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.
An example of a recursive function [math]f(n)[/math] is:
- If [math]n \gt 0[/math] then return [math]n \times f(n-1)[/math].
- If [math]n = 0[/math] then return [math]1[/math].
The definition has two cases: a recursive case for [math]n\gt 0[/math], and a case for [math]n=0[/math] that is not recursive. The case that is not recursive is called a "base case".
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.
- A fractal image contains smaller versions of itself.
- In the rules of grammar, a sentence can be part of another sentence.