Линейная рекурсия
Простейшим примером рекурсии является линейная рекурсия, когда функция содержит единственный условный вызов самой себя. В таком случае рекурсия становится эквивалентной обычному циклу. Действительно, любой циклический алгоритм можно преобразовать в линейно-рекурсивный и наоборот. Продемонстрируем это на примере вычисления факториала :
// Рекурсивный алгоритм
int fact(int n)
{
if (n==1) return 1;
return n * fact(n-1);
}
// Циклический алгоритм
int fact(int n)
{
for (int s=1; n!=0; n--) s *=n;
return s;
}
