Cтраница 4
Первая пара этих равенств дает рекурсивное определение сама по себе, а вторая - в том случае, если она вводится после первой. [46]
Из этих соотношений следуют также простые рекурсивные определения, вытекающие непосредственно из рекурсивных определений деревьев и бинарных деревьев. Приведенные соотношения также непосредственно связаны с анализом рекурсивных алгоритмов. Например, для многих рекурсивных вычислений высота соответствующего дерева в точности равна максимальной глубине рекурсии, или размеру стека, необходимого для поддержки вычисления. [47]
Рассмотренная формула представляет собой пример рекурсивного определения, когда сам термин определяемого понятия используется для получения некоторых своих собственных значений. При этом он может непосредственно встречаться в правой части формулы своего определения, Тем самым уже известные значения понятия служат основой для получения новых значений того же понятия. [48]
Однако с помощью еще одного рекурсивного определения можно добиться, чтобы было учтено и это обстоятельство. [49]