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

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

 → Рекурсия

Схема примитивной рекурсии — это алгоритм определения вида функции 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.

СПР11.JPG

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

[править] Пример 2

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

СПР12.JPG

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

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

[править] Ссылки

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

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