Методы разрешения рекуррентности

Самый естественный и понятный подход к поиску решения — «раскрутка» ре- курсии с отслеживанием времени выполнения на нескольких начальных уровнях и выявлением закономерности, которая сохраняется в ходе рекурсии.

Во втором варианте строится гипотеза, которая подставляется в рекуррентное отношение и проверяется на жизнеспособность. Для формальной проверки таких подстановок используется индукция по n. Существует полезная разновидность этого метода, в которой известна общая форма решения, но неизвестны точные зна- чения всех параметров. Оставляя эти параметры неопределенными в подстановке, часто удается подобрать их по мере необходимости.

А теперь мы обсудим каждый из этих методов на примере рекуррентного от- ношения (5.1).