Рекурсия. В языке С++ допустимо рекурсивное определение функций, при котором функция может вызывать сама себя

В языке С++ допустимо рекурсивное определение функций, при котором функция может вызывать сама себя. Надо сказать, что такие функции работают медленнее, чем нерекурсивные. Однако они незаменимы при обработке динамических структур, например деревьев.

Пример. Вычислить сумму факториалов целых чисел, принадлежащих отрезку [m;n].

Это классическая задача, которую можно решить с использованием рекурсивной функции.

Ход выполнения работы

1. В файле f.h опишем рекурсивную функцию, вычисляющую факториал числа n:

int fact(int n)

{

if(n= =0 || n= =1) return 1;

else

return n*fact(n-1);

}

Как видно, среди операторов тела функции происходит ее вызов, т.е. функция является рекурсивной.

В файле главной функции запишем основной алгоритм решения задачи на языке С++:

#include "stdio.h"

#include "stdlib.h"

#include "iostream.h"

#include "iomanip.h"

#include "f.h"

int main()

{

int i, n, m, s;

cout<<"Введите границы отрезка m=";

cin>>m;

cout<<"n=";

cin>>n;

if(m<n)

{

//вычислим сумму

s=0;

for(i=m; i<=n; i++)

//вызываем функцию fact(); ее аргумент изменяется в цикле

s=s+fact(i);

//выведем значение суммы на экран

cout<<"summa="<<s<<endl;

}

else

cout<<"Границы отрезка введены неверно"<<endl;

return 1;

}

Примечание. При вычислении 4! функция fact() будет вызывать сама себя три раза следующим образом:

4*fact(3)

3*fact(2)

2*fact(1)

Как только значение параметра этой функции достигнет 1, результат ее работы будет вычисляться в обратном порядке:

2*1=2

3*2=6

4*6=24