РЕКУРСИВНОЕ ОПРЕДЕЛЕНИЕ (от лат. 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. В основе вычислимости арифметических функций, определяемых рекурсивно, лежит класс некоторых других функций, считающихся заданными с самого начала, которые называются примитивно-рекурсивными.