|
НАЗАД
Все рекурсивные алгоритмы в целом имеют ряд свойств, которые объединяют их с «рекурсивными структурами данных» и «рекурсивными определениями», рассмотренными выше. Прежде всего, рекурсия может быть косвенной:программа а (аргумент х: ...)
b(f(x)) (f(x)-выражение, зависящее от х);
…
программа b (аргумент у: ...)
…
a(g(y)) (g(у)-выражение, зависящее от у};
…
Другое важное условие, касающееся использования рекурсии, состоит в том, что объекты, порожденные рекурсивным определением (будь то информационные структуры или вычисления), должны быть конечными. Следовательно, вся совокупность рекурсивных подпрограмм должна включать такое положение, при котором в определенных случаях вычисление могло бы делаться непосредственно, без рекурсивного вызова. Одна из подпрограмм по крайней мере должна будет, следовательно, иметь общий вид:
еслиCто Апрям {действие или выражение, выполняемое непосредственно}
иначе Врек{часть, включающая при необходимости рекурсивные вызовы}
или
пока ¬C повторять Врек; (знак «¬» означает отрицание)
Апрям
или некоторую эквивалентную форму. Для того чтобы выполнение соответствующей подпрограммы могло быть завершено, необходимо, следовательно, чтобы существовала некоторая связанная с этой программой управляющая величина m, т.е. целое неотрицательное число, относительно которого можно было бы с уверенностью сказать, что оно строго убывает при каждом рекурсивном вызове. В простейших случаях роль такой управляющей величины может играть один из параметров подпрограммы. Так, любая подпрограмма, отвечающая следующей схеме:
программаnn (аргументы n: ЦЕЛ, х, у, z: ...)
еслиn = 0 то
Апрям(n, х, у, z, ...) {без рекурсивного вызова}
иначе
Врек{где все рекурсивные вызовы имеют вид
nn(п - 1, f(x), g(y), h(z)...)}
после конечного числа рекурсивных вызовов выдаст определенный результат для каждого неотрицательного аргумента n,
Примером такого рекурсивного вычисления, не связанного с проблемой конечности (для m ≥0, n ≥ 0), является вычисление коэффициентов треугольника Паскаля, рассмотренное выше. Очевидно, что управляющей величиной в этом случае является n.
Однако в общем случае ситуация не всегда столь удобна и управляющая величина не всегда так просто выражается.
Еще более важной в теории вычислений является теорема, утверждающая, что нет никакого общего метода, определяющего, дает ли результат произвольная рекурсивная подпрограмма р, примененная к произвольному данному q, после конечного числа этапов, дающего подобный результат для цикла «пока».
Исследование частичных свойств завершимости рекурсивных вычислений представляет собой важную область теории вычислений. Показано, что способ передачи параметров влияет на завершимость программ: передача по имени является, например, более «надежной», чем передача значением. Действительно, вычисление параметра, передаваемого значением, может «расходиться», тогда как вызываемая подпрограмма не использует этот параметр.
НАЗАД Читать ДАЛЕЕ
|
