Рекурсивная функция

---

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция ${\displaystyle f(n)}$ числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения ${\displaystyle f(n)}$ на основе значений ${\displaystyle f(n-1),f(n-2),\ldots }$, подобно рассуждению по индукции. Чтобы вычисление завершалось для любого ${\displaystyle n}$, необходимо, чтобы для некоторых ${\displaystyle n}$ функция была определена нерекурсивно (например, для ${\displaystyle n=0,1}$).

${\displaystyle F={\begin{cases}F(0)=0;\\F(1)=1;\\F(n)=F(n-1)+F(n-2),\quad n>1.\end{cases}}}$^[1]

Руководствуясь этой записью, мы можем вычислить ${\displaystyle F(n)}$ для любого натурального n за конечное число шагов. Правда, по пути придётся дополнительно вычислить значения ${\displaystyle F(n-1),F(n-2),\ldots ,F(2)}$.

В связи с накладными расходами полезно знать, есть ли у рекурсивной функции нерекурсивная (замкнутая) форма.

---