рекурсивни функции

Може да се приеме с известно приближение твърдението, че рекурсия и итерация са еквивалентни. Има редица случаи, при които намирането на итеративно решение е изключително трудоемко и тогава използването на рекурсивни функции е по-лесният изход. Такива примери са задачата за бързо сортиране, задачата за Ханойските кули и др.

Типичен случай за обратния вариант е изчисляване числа на Фибоначи и свързаните с тях редици. При тях използването на рекурсия е само за демонстрация на неефективен алгоритъм.

Смисълът на определението ефективна програма не е непременно свързан с итеративен или рекурсивен алгоритъм. Използването на асиптотичен алгоритъм (Master theorem) позволява получаване на резултат с удовлетворяваща точност при съществено намаляване изискванията за необходимия хардуерен ресурс. Пример за това е изчисляване сума на геометрична прогресия.

Sum = a^0 + a^1 + a^2 +….+ a^n,

при a < 1 стойността на сумата се приближава към стойността на отношението 1/(1-a);

при a = 1 стойността на сумата е равна на n;

Терминът рекурсивна програма се отнася за програма съдържаща една или повече рекурсивни функции.