Функции в С++ для начинающих. Рекурсия. Вычисление факториала числа с помощью рекурсии

Опубликовано 06.04.2012 | Автор: admin

Один из стандартных примеров — пример рекурсивного вычисления факториала. Мне этот пример мало нравится, но коли его так любят давать, то пусть будет и на моём сайте.

К сведению:

Факториал числа — это произведение всех натуральных чисел от 1 до n включительно.

Для понимания примера необходимо знать:

Пример кода:

//Рекурсия		Пример вычисления факториала
#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();
}

//Рекурсия Пример вычисления факториала

#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

Рекурсия имеет много недостатков. Она многократно активирует механизм вызовов — отсюда рост "накладных расходов". Они могут оказаться слишком расточительными как в плане процессорного времени, так и в плане объема памяти. Каждый рекурсивный вызов приводит к созданию нового экземпляра функции (на самом деле создаются только новые экземпляры её переменных). На это может расходоваться значительная память.

Любую задачу, которая может быть решена рекурсивно, можно решить и итеративно (нерекурсивно). Обычно рекурсивный подход предпочитают итеративному, если он более естественно отражает задачу и дает в результате программу, которую проще понять и отладить. Другая причина выбора рекурсивного решения может состоять в том, что итеративное решение оказывается неочевидным.

Избегайте использования рекурсии в случаях, требующих высокой эффективности. Рекурсивные вызовы требуют времени и дополнительных затрат памяти.

Рубрика: Решения задач, Функции

ww:

22.04.2013 в 7:17 дп

Неточности во втором листинге.
в прототипе функции д.б. переменная задана со строчной (int n)
условие д.б. в скобках if (n<2)
отсутствует закрывающая фигурная скобка у функции main }

и в теле рекурсивной функции else return n*fact(n-1) д.б. точка с запятой, спасибо.

Ответить

Функции в С++ для начинающих. Рекурсия. Вычисление факториала числа с помощью рекурсии

Один комментарий на «“Функции в С++ для начинающих. Рекурсия. Вычисление факториала числа с помощью рекурсии”»

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета