РЕКУРСИВНОЕ ОПРЕДЕЛЕНИЕ (от лат.
recurso - возвращаюсь) — метод определения арифметической функции
φ(
у)
или
предиката Р(
у)
через область значений этой функции или предиката. Примером Р. о. может быть определение функции сложения:
а + 0 = а,
(1)
а + b‘=(
а+b)
‘ (2) В равенстве (1) говорится, что некоторое фиксированное число
а (см.:
Параметр)
при прибавлении к нему нуля дает число
а.
В равенстве (2) говорится., что если к некоторому фиксированному числу
а добавить число, следующее за некоторым фиксированным числом
b (т. е.
b‘,
или число
b+1), то эта сумма будет равна числу, следующему за суммой чисел
а+b.
Напр., если к числу 2 добавить число, следующее за числом 3, т. е. число 4, то этот же результат можно получить, сложив 2 и 3 и перейдя от полученной суммы к следующему за ней числу. Значение левой и правой частей равенства в данном случае равно 6. Такого рода функции позволяют вычислять значение суммы самых различных чисел. При этом осуществляется переход от некоторого числа
п к следующему за ним (к
п‘,
или
п+1), т. е. строится натуральный ряд чисел начиная с нуля. Допустим, нам требуется сложить 5 и 2. Тогда число 2 представим как следующее за 1, т. е. как 1‘. Итак, имеем:
| а)5+2=5+1‘=(5+1)‘ б)5+1=5+0‘=(5 + 0)‘ | } | по равенству (2), |
| в) 5+0=5 — по равенству (1). |
Теперь будем
возвращаться от равенства 5+0=5 (в) к равенству (б), а затем к равенству (а). Раз 5+0=5, то (5+0)‘=6 (см. равенство (б)). Раз 5+1 равно 6, то (5+1)‘=7 (см. равенство (а)). Итак, 5+2=7. В основе вычислимости арифметических функций, определяемых рекурсивно, лежит класс некоторых других функций, считающихся заданными с самого начала, которые называются примитивно-рекурсивными.