Этот тип рекурсии определяется как дополнительный к линейному. Иными словами, рекурсию называют каскадной, если она не является линейной. Мы уже имели примеры каскадных рекурсий: непосредственная реализация рекурсивных вычислений чисел Фибоначчи и биномиальных коэффициентов, подсчет количества разбиений натурального числа на сумму натуральных слагаемых. Еще один пример каскадной рекурсии задает функция
которая вычисляет значения многочленов Чебышева для заданного
n при фиксированном или произвольном x. В последнем случае используются символьные вычисления. Функция T(n,x) реализована исходя из известной рекуррентной формулы:Tn+1(x)=2× x× Tn(x)- Tn- 1(x) (n=1, 2, …; T0(x)=1, T1(x)=x).
Контрольные примеры:T(5,2)=362, T(5,x) simplify ® 16× x5- 20× x3+5× x,
T(10,x) simplify ® 512× x10- 1280× x8+1120× x6- 400× x4+50× x2- 1.
При каскадной рекурсии, рекурсивные обращения, как правило, приводят к необходимости многократно решать одни и те же подзадачи. И поэтому, по возможности, от неё или следует избавляться или предпринимать шаги, освобождающие от необходимости производить повторные решения подзадач.
