Информатика • 9 класс

Рекурсия (С++)

Рекурсивная функция — это функция, которая вызывает сама себя напрямую или через другие функции.
Такой способ описания функции называется рекурсия.
Рекурсивная функция обязательно должна содержать в себе условие окончания рекурсивности, чтобы не вызвать зацикливания программы. Например, вызов функции внутри неё самой можно разместить в операторе if.
Любую рекурсивную функцию можно записать без рекурсии с помощью цикла.
Программный код с рекурсией изящнее и проще для понимания, но занимает больше памяти и дольше выполняется.

Пример. Вычислите факториал числа N:

$N! = \{\begin{matrix} 1, N = 1 \\ N \cdot (N - 1)!, N > 1 \end{matrix}$

Решение.

int fact (int n) {
  if (n <= 1)
    return 1;
  else
    return n * fact (n - 1); }

Было полезно?