Виды рекурсии
→ Рекурсия
Рекурсия — это метод определения понятия, определяемого через само себя.
Виды рекурсии:
- рекурсивная формула;
- рекурсивная функция;
- рекурсивная последовательность;
- рекурсивный алгоритм;
- рекурсивная программа;
- рекурсивное изображение.
Основные определения[править]
Рекурсивная формула — это рекуррентная формула, то есть содержащая в себе саму себя или формулы, содержащие в их формулах её (рекуррентную формулу).
Рекурсивная функция — это функция, определяемая рекуррентной формулой или содержащая функции, содержащие в их формулах её (рекурсивную функцию).
Рекурсивная последовательность — это последовательность, члены которой определяются по рекуррентной формуле.
Рекурсивный алгоритм — это алгоритм, содержащий в себе обращение к самому себе или к алгоритмам, содержащим обращение к нему (рекурсивному алгоритму).
Рекурсивная программа — это программа, содержащая в себе обращение к самой себе или к программам, содержащим обращение к ней (рекурсивной программе).
Рекурсивное изображение — это изображение, содержащее в себе своё уменьшенное изображение.
Примеры рекурсивных функций[править]
Пример 1. — это функция «факториал».
Свойства функции:
Пример 2.
Свойства функции:
Другие алгоритмы[править]
- метод математической индукции;
- алгоритмы в арифметике;
- алгоритмы перевода чисел;
- комбинаторные алгоритмы;
- сортировка;
- алгоритм определения мест;
- логистические алгоритмы;
- алгоритмы решения транспортных задач;
- численные методы;
- схема примитивной рекурсии;
- виды рекурсии;
- машина Поста;
- машина Тьюринга (вероятностная);
- синтез автомата Мили;
- синтез автомата Мура.