Виды рекурсии

 → Рекурсия

Рекурсия — это метод определения понятия, определяемого через само себя.

Виды рекурсии:

• рекурсивная формула;
• рекурсивная функция;
• рекурсивная последовательность;
• рекурсивный алгоритм;
• рекурсивная программа;
• рекурсивное изображение.

Основные определения

Рекурсивная формула — это рекуррентная формула, то есть содержащая в себе саму себя или формулы, содержащие в их формулах её (рекуррентную формулу).

Рекурсивная функция — это функция, определяемая рекуррентной формулой или содержащая функции, содержащие в их формулах её (рекурсивную функцию).

Рекурсивная последовательность — это последовательность, члены которой определяются по рекуррентной формуле.

Рекурсивный алгоритм — это алгоритм, содержащий в себе обращение к самому себе или к алгоритмам, содержащим обращение к нему (рекурсивному алгоритму).

Рекурсивная программа — это программа, содержащая в себе обращение к самой себе или к программам, содержащим обращение к ней (рекурсивной программе).

Рекурсивное изображение — это изображение, содержащее в себе своё уменьшенное изображение.

Примеры рекурсивных функций

Пример 1. $f(n)={\begin{cases}1,\ n=0\\nf(n-1),\forall n\in \mathbb {N} \end{cases}}$ — это функция «факториал».

Свойства функции:

$f(0)=1;\ f(1)=1;\ f(2)=2;\ f(3)=6;\ldots ;f(n)=n!$

Пример 2. $f(n)={\frac {n}{n+f(n+1)}},\ \forall n\in \mathbb {N} \cup \{0\}$

Свойства функции:

$f(0)=0;\ f(1)={\frac {1}{e-1}};\ f(2)=e-2;\ f(3)={\frac {6-2e}{e-2}};\ldots ;$

$f(n+1)={\frac {n}{f(n)}}-n$

$\lim _{n\to \infty }f(n)=1$

Другие алгоритмы

• метод математической индукции;
• алгоритмы в арифметике;
• алгоритмы перевода чисел;
• комбинаторные алгоритмы;
• сортировка;
• алгоритм определения мест;
• логистические алгоритмы;
• алгоритмы решения транспортных задач;
• численные методы;
• схема примитивной рекурсии;
• виды рекурсии;
• машина Поста;
• машина Тьюринга (вероятностная);
• синтез автомата Мили;
• синтез автомата Мура.