Функции в С++ для начинающих. Рекурсия. Вычисление факториала числа с помощью рекурсии
Один из стандартных примеров — пример рекурсивного вычисления факториала. Мне этот пример мало нравится, но коли его так любят давать, то пусть будет и на моём сайте.
К сведению:
- Факториал числа — это произведение всех натуральных чисел от 1 до n включительно.
Для понимания примера необходимо знать:
Пример кода:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
//Рекурсия Пример вычисления факториала #include <iostream> using namespace std; int factorial(int value){ //0! = 1; 1! = 1; 2! = 2; 3! = 6... //Т. к. первые два числа единицы, контрольной точкой сделаем единицу if (value < 2){ return 1; //1! = 1, поэтому return 1 } else { return factorial(value - 1) * value; //Иначе создаём ещё оие эуземпляр функции с новым значением параметру }; } int main(){ int N = 5; cout << factorial(N); //выводим на экран факториал N cin.ignore().get(); } |
Внутри функции factorial происходит основное вычисление. При этом внутренность функции делится на две части: проверка на необходимость прекращения и на запуск нового экземпляра функции, провоцирующего вычисление. При этом смешивается вычисляемое функцией число, на основе отданного в функцию аргумента, и значение параметра функции: вы видите формулу factorial(value — 1) * value, в которой вычисляемое дополнительной функцией factorial число factorial(value — 1) умножается на значение параметра текущей функции: value. Эта смесь может немного путать, но её несложно научиться различать. Если происходит вызов функции, то, получается, значение вычисляется функцией, а если мы задействуем просто значение параметра, то оно и есть значение, пришедшее в параметр текущей функции.
Вычисление факториала для первых нескольких чисел:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
- Рекурсия имеет много недостатков. Она многократно активирует механизм вызовов — отсюда рост "накладных расходов". Они могут оказаться слишком расточительными как в плане процессорного времени, так и в плане объема памяти. Каждый рекурсивный вызов приводит к созданию нового экземпляра функции (на самом деле создаются только новые экземпляры её переменных). На это может расходоваться значительная память.
- Любую задачу, которая может быть решена рекурсивно, можно решить и итеративно (нерекурсивно). Обычно рекурсивный подход предпочитают итеративному, если он более естественно отражает задачу и дает в результате программу, которую проще понять и отладить. Другая причина выбора рекурсивного решения может состоять в том, что итеративное решение оказывается неочевидным.
- Избегайте использования рекурсии в случаях, требующих высокой эффективности. Рекурсивные вызовы требуют времени и дополнительных затрат памяти.
Один комментарий на «“Функции в С++ для начинающих. Рекурсия. Вычисление факториала числа с помощью рекурсии”»
Добавить комментарий
Случайная книга в электронном формате
Неточности во втором листинге.
в прототипе функции д.б. переменная задана со строчной (int n)
условие д.б. в скобках if (n<2)
отсутствует закрывающая фигурная скобка у функции main }
и в теле рекурсивной функции else return n*fact(n-1) д.б. точка с запятой, спасибо.