Рекурсивные функции. Тезис Черча. Способы реализации рекурсии

Рекурсия является одним из мощнейших средств современных языков программирования. Схема рекурсии:

,

где f – функция от (n + 1)-ой переменной, g - функция от n переменных, h - функция от (n + 2)-х переменных. При n = 0 схема рекурсии имеет вид:

.

Схема рекурсии полностью определяет функцию f. Рекурсия похожа не метод доказательства теорем по индукции, причём индукция проводится по переменной y. Сначала задаётся первый шаг индукции (f(0)), а затем из шага номер y (f(y)) вычисляется шаг номер (y+1) (f(y+1)).

Тезис Чёрча: всякая вычислимая функция является рекурсивной. Без доказательства. Другими словами, всякая аналитическая функция может быть задана и рекурсивно.

Регрессия – это один из способов обработки данных, заданных двумя векторами одинаковой длины (вектор x и вектор y).