Mathematically, a
recursive function is a
function that
defines itself in terms of
itself. No, it's not as hopelessly
confusing as it appears.
for instance, take this function:
f(n)=4*
f(n-1)
This would be impossible to compute unless you set a lower limit, such as
f(1)=1...
In that case, you'd get the following values.
in | out
1 | 1
2 | 4
3 | 16
4 | 64
...
This gets annoying, however, if you need to find a term that is greater than about five, in which case, you are
buried in numbers. Then, you turn to a
programmable calculator.
Even though functions are typically referred to as
f(
x), to show that it is a recursive function, it is
standard to use
n instead.
Recursive functions can define themselves in terms of the previous (or next, in which case you'd need to define
upper limits) TWO (or more, to infinity) functions... such as:
f(n)=3*
f(n-1) -
f(n-2)
f(0)=0;
f(1)=2=
which would give the following results:
in |out
0 |0
1 |2
2 |6
3 |16
4 |46
5 |138
...