Иногда возможно сформулировать решение задачи как известное преобразование другого, более простого, варианта той же задачи. Если этот процесс продолжить до тех пор, пока не получится нужное значение, то подобное решение называется рекурсивным.
Примером рекурсивного решения является вычисление факториала fact(N) = 1×2×…×N. Пусть неизвестно значение fact(460), если умножить fact(459) на 460, тогда задача сводится к вычислению fact(459). Если это преобразование далее повторить 458 раз, то можно вычислить значение факториала, поскольку fact(1) = 1. Таким образом, функция F является рекурсивной, если:
1) F(N) = G(N, F(N – 1)) для некоторой известной функции G и
2) F(1) равно некоторому известному значению.
Функция F может быть функцией нескольких параметров. Значение N должно быть задано в явном виде. Величина N может быть элементом во множестве, длиной интервала или некоторым другим параметром.
Рекурсивное решение всегда записывается проще, чем соответствующий нерекурсивный вариант. Относительно скорости решения однозначных выводов сделать нельзя. Это зависит от сложности функции G.