Functions defined by
recursion (or induction) are usually discussed only after a
beginning course in algebra.
They play a role both in the definition of sequences of numbers and
functions usually given a more thorough treatment in calculus
courses.
For example, suppose the function $ f_{ \Sigma k}: N
\rightarrow N$ is defined recursively, by $f_{ \Sigma k}(0)=
0$ and $f_{ \Sigma k}(n+1)= n+ 1 +f_{ \Sigma k}(n)$ for all $n \ge
0$. Then this function can also be characterized by $f_{
\Sigma k}(n) = \frac {n*(n+1)} 2$.
Another example was demonstrated with the factorial function, $f : N
\rightarrow N$. This function is defined by $f(0)=1$ and
$f(n+1)=(n+1) \times f(n)$ for all $n \ge 0$ which can also be
expressed with an elliptic notation: $f(0) = 1; f(n) = n*(n-1)* ...
* 2*1$ for $n >0$.
An example of the use of recursion to define a family of
functions $f_n : R \rightarrow R$ is given in Example OW.RECF.4.
The following examples show some of the ways functions defined by
recursion can be visualized with mapping diagrams.
Example OW.RECF.2
: $ f_{ \Sigma k}: N \rightarrow N$
$f_{ \Sigma k}(0)= 0$ and $f_{ \Sigma k}(n+1)= n+ 1 +f_{ \Sigma
k}(n)$ for all $n \ge 0$.
Example OW.RECF.3
:
$f: N \rightarrow N$ .
Choose $r \in R$. $f(0)= 1$ and $f(n+1)= 1 + r* f(n)$ for all $n
\ge 0$.
Generalized: Choose $r \in R$. $f_a(0)= a$ and $f_a(n+1)= a + r*
f(n)$ for all $n \ge 0$.
Example OW.RECF.4
:
$f_n: R \rightarrow R$ .
Choose $x \in R$. $f_0(x)= 1$ and $f_{n+1}(x)= 1 + x* f_n(x)$ for
all $n \ge 0$.
Example
OW.DRECF.0 :
Dynamic Visualization of the Recursive Functions: Graphs and
Mapping Diagrams