Рекурсия

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

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

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

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

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

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

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

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

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

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

Пример 1

- это функция "факториал".

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

Пример 2

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

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

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

Ссылки

• Википедия. Рекурсия.
• Участник:Logic-samara