БЕСПЛАТНОЕ РЕШЕНИЕ ЗАДАЧ

Факториал числа с рекурсией в С++

Под рекурсией подразумевают вызов в теле функции этой же самой функции. Рекурсивный вызов может быть как прямым (функция вызывается в теле этой же функции), так и непрямым или косвенным (в функции вызывают­ся другие функции, в теле которых, в свою очередь, вызывается исходная функция). Обычно к такому приему прибегают, когда программируемая последовательность действий может быть сформулирована в терминах рекурсивной зависимости как последовательность значений, каждое из которых определяется на основе предыдущего по одной и той же схеме или принципу. В качестве примера использования рекурсии рассмотрим программу по вычислению факториала числа. Напомним, что факториал числа определяется как произведение всех натуральных чисел от единицы до этого чис­ла включительно:
$$n!=1\cdot 2\cdot 3\cdot 4\cdot...\cdot n$$
Но, такая формула не очень удобна, поэтому воспользуемся формулой, полученной из этой и позволяющей вычислять последующее значение факториала на основе предыдущего:
$$n!=\left(n-1 \right)!\cdot n$$
Эту формулу уже можно использовать для рекурсивного вычисления факториала. Пример такой программы приведен в следующем листинге.
#include 
using namespace std;
int factorial(int n){
if(n==1) return 1;
else return n*factorial(n-1);
}
int main(){
int n;
cout << "Enter n = ";
cin >> n;
cout << "n! = " << factorial(n) << endl;
return 0;
}
Целочисленная функция factorial(int n) достаточно простая: у нее всего один целочисленный аргумент п, а тело кода состоит из условного опера­тора. Проверяемым является условие п—1, при выполнении которого воз­ вращается значение 1 (следствие того замечательного факта, что факториал единицы равен единице, то есть 1! = 1). Если аргумент у функции не единичный, значение вычисляется в виде выражения n*factorial(n-1). В этом выражении вызывается определяемая функция, но с уменьшенным на единицу аргументом. При вычислении значения функции возможны два варианта: аргумент единичный и аргумент больше единицы (другие варианты не рассматриваем в принципе). Если аргумент единичный - все просто. В качестве зна­чения возвращается число 1. В противном случае для вычисления значе­ния функции вызывается эта же функция, но только аргумент у нее на единицу меньше. Если после уменьшения на единицу аргумент все равно не единичный, снова вызывается функция, и ее аргумент еще на единицу меньше и т.д. до тех пор, пока аргумент у вызываемой функции не станет единичным. Для единичного аргумента значение вычисляется «в лоб», по­сле чего вся эта цепочка последовательных вызовов раскручивается в обратном порядке. Отметим, что, несмотря на эффектность программного кода с рекурсивным вызовом, эффективностью он отличается редко, поскольку требует исполь­зования существенных системных ресурсов.

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

Вы должны быть авторизованы , чтобы оставить или оценить комментарий.

Онлайн всего: 3
Гостей: 3
Пользователей: 0

STUDLAB Сообщить про опечатку на сайте