Recursive function

The recursive function (from lat. Recursio - return) is a numerical function $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ a numerical argument, which in its record contains itself. This record allows you to calculate the values $f(n)$ ${\ displaystyle f (n)}$ $f (n)$ based on values $f(n-1),f(n-2),\ldots$ ${\ displaystyle f (n-1), f (n-2), \ ldots}$ $f (n-1), f (n-2), \ ldots$ , similar to reasoning by induction . To make the calculation complete for any $n$ ${\ displaystyle n}$ $n$ , it is necessary that for some $n$ ${\ displaystyle n}$ $n$ the function was defined non-recursively (e.g. for $n=0,1$ ${\ displaystyle n = 0,1}$ $n = 0.1$ )

Examples

An example of a recursive function giving the nth Fibonacci number :

$F={\begin{cases}F(0)=1;\\F(1)=1;\\F(n)=F(n-1)+F(n-2),\quad n>1.\end{cases}}$ ${\ displaystyle F = {\ begin {cases} F (0) = 1; \\ F (1) = 1; \\ F (n) = F (n-1) + F (n-2), \ quad n> 1. \ end {cases}}}$ $F={\begin{cases}F(0)=1;\\F(1)=1;\\F(n)=F(n-1)+F(n-2),\quad n>1.\end{cases}}$

Guided by this record, we can calculate $F(n)$ ${\ displaystyle F (n)}$ $F(n)$ for any positive integer n in finitely many steps. True, along the way you have to additionally calculate the values $F(n-1),F(n-2),\ldots ,F(2)$ ${\ displaystyle F (n-1), F (n-2), \ ldots, F (2)}$ $F(n-1),F(n-2),\ldots ,F(2)$ .

Closed form

In connection with overhead, it is useful to know if a recursive function has a non-recursive (closed) form.

The closed form may not be found for all recursive functions (relations). For some of them, only approximate closed forms were found. Some recursive relationships, such as factorial , are considered elementary mathematical operations.

For example, a recursive function that describes the sum of numbers in a natural series:

$f={\begin{cases}f(0)=0;\\f(n)=n+f(n-1),\quad n>0\end{cases}}$ ${\ displaystyle f = {\ begin {cases} f (0) = 0; \\ f (n) = n + f (n-1), \ quad n> 0 \ end {cases}}}$ $f={\begin{cases}f(0)=0;\\f(n)=n+f(n-1),\quad n>0\end{cases}}$

can be translated into closed form: $f={\frac {n(n+1)}{2}}$ ${\ displaystyle f = {\ frac {n (n + 1)} {2}}}$ $f={\frac {n(n+1)}{2}}$ .

Applications

Recursive functions play an important role in the theory of algorithms , since many algorithms have a recursive structure.

Recursive function

Examples

Closed form

Applications

More articles: