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

 → Рекурсия

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

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

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

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

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

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

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

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

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

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

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

Пример 1. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(n) = \begin{cases} 1, \ n=0 \\ nf(n-1), \forall n \in \mathbb{N} \end{cases} } — это функция «факториал».

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(0)=1; \ f(1)=1; \ f(2)=2; \ f(3)=6;\ldots ; f(n)=n!}

Пример 2. Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(n)=\frac{n}{n+f(n+1)}, \ \forall n \in \mathbb{N}\cup \{0\}}

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(0)=0; \ f(1)=\frac{1}{e-1}; \ f(2)=e-2; \ f(3)=\frac{6-2e}{e-2};\ldots ;}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle f(n+1)=\frac{n}{f(n)}-n}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \lim_{n \to\infty}f(n)=1}

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

1. методы доказательств;
2. алгоритмы в арифметике;
3. алгоритмы перевода чисел;
4. комбинаторные алгоритмы;
5. сортировка;
6. алгоритм определения мест;
7. логистические алгоритмы;
8. алгоритмы решения транспортных задач;
9. численные методы;
10. рекурсия;
11. схема примитивной рекурсии;
12. виды рекурсии;
13. машина Поста;
14. машина Тьюринга (вероятностная);
15. синтез автомата Мили;
16. синтез автомата Мура.