На этом шаге мы рассмотрим случай косвенной рекурсии.
Если две процедуры A и B связаны косвенной (взаимной) рекурсией, то для каждой из них можно записать выражения функции сложности и объединить их в общую систему уравнений. Поскольку одна из процедур, например, B имеет нерекурсивную ветвь, то эта ветвь порождает начальные условия. В простом случае однократного вызова процедуры B в теле A (и процедуры A в теле B) уравнения имеют вид:
TA(X) = ТB(fA(X)) + TfA(Х)+ ТhA(X), ТB(X) = ТA(fB(X)) + ТfB(Х)+ ТhB(X) + ТcВ(X, S), TB(S) = TcB(S,S) + TsB(S)
Первые два уравнения с двумя неизвестными функциями могут быть подстановкой во второе уравнение вместо TA правой части первого уравнения (с соответствующим изменением аргумента) сведены к одному уравнению для определения TB. Третье уравнение останется в качестве начального условия. Таким образом, задача определения функции сложности в случае косвенной рекурсии будет сведена к той же задаче для прямой рекурсии.
На следующем шаге мы рассмотрим особые случаи анализа сложности рекурсивных алгоритмов.
