Рекурсия предстовляет из себя вызов некоторой функции в своём собственном теле. С помощью рекурсии можно весьма эффективно решать некоторые задачи. Для описания принципа её работы сразу рассмотрим пример:
Code
int fact(int n)
{if(n <= 1)
return 1;
return fact(n-1)*n;
}
Теперь посмотрим что произойдет если мы вызовем её с параметром 3. Результат есть 6 = 3! - не трудно понять, что это функция вычисляет факториал и от других натуральных чисел (в случае если параметр число ненатуральное или ноль возвращает 1). Таким образом мы имеем рекурсивную реализацию для функции вычисления факториала.
Приведём ещё пример функции для вычисления наибольшего общего делителя двух чисел:
Code
int nod(int a, int b)
{if(a%b == 0)
return b;
return nod(b, a%b);
}
Функция основана на алгоритме Евклида и её я предлагаю разобрать самостоятельно, в качестве упражнения.
Задания:
1) Вручную просчитать работу fact от 6.
2) Разобрать алгоритм нахождения наибольшего общего делителя.
3) Написать рекурсивную реализацию функции для вычисления суммы квадратов чисел от 0 до n.
