Схема примитивной рекурсии

 → Рекурсия

Схема примитивной рекурсии — это алгоритм определения вида функции f(x, y) на основе известных функций φ(x) и ψ(x, y, z), причём f(x, 0) = φ(x), а f(x, n) = ψ(x, n-1, f(x, n-1)).

Алгоритм

Входные данные: n; φ(x); ψ(x, y, z).

1. Определяем выражения функции f(x, y).
f(x,0) = φ(x)
f(x,1) = ψ(x,0,f(x,0))
f(x,2) = ψ(x,1,f(x,1))
…,
f(x,n−1) = ψ(x,n−2,f(x,n−2))
f(x,n) = ψ(x,n−1,f(x,n−1))

2. По аналогии определяем формулу f(x, y).

3. Методом математической индукции доказываем формулу f(x, y), проведя индукцию по y.

Выходные данные: f(x, y).

Примеры работы алгоритма

Пример 1

Входные данные: n = 3; φ(x) = x; ψ(x, y, z) = xz.

Выходные данные: f(x, y) = x^y+1.

Пример 2

Входные данные: n = 3; φ(x) = 0; ψ(x, y, z) = x + y.

Выходные данные: f(x, y) = x + y - 1.

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

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

Ссылки

• Участник:Logic-samara