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

Материал из Циклопедии
Перейти к: навигация, поиск

 → Рекурсия

Лекция 6: Сопоставление с образцом. Рекурсия. Циклы // НОУ ИНТУИТ [25:06]

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

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

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

[править] Основные определения

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

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

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

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

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

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

[править] Примеры рекурсивных функций

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

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

[math]f(0)=1; \ f(1)=1; \ f(2)=2; \ f(3)=6;\ldots ; f(n)=n![/math]

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

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

[math]f(0)=0; \ f(1)=\frac{1}{e-1}; \ f(2)=e-2; \ f(3)=\frac{6-2e}{e-2};\ldots ;[/math]
[math]f(n+1)=\frac{n}{f(n)}-n[/math]
[math]\lim_{n \to\infty}f(n)=1[/math]

[править] Другие алгоритмы

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты