Рекурсия Простейшие рекурсивные алгоритмы

Рекурсия

Простейшие рекурсивные алгоритмы

Задания этого раздела можно легко решить и без использования рекурсии. Данное обстоятельство связано с тем, что в заданиях рассматриваются простейшие примеры рекурсии, легко сводимые к итерационным алгоритмам. Более того, в некоторых случаях непосредственные вычисления по рекурсивным формулам оказываются весьма неэффективными (см., например, задания Recur4 и Recur6). Однако именно на подобных примерах проще всего получить первоначальные навыки разработки рекурсивных алгоритмов.
Recur2. Описать рекурсивную функцию Fact2(N) вещественного типа, вычисляющую значение двойного факториала
N!! = N·(N−2)·(N−4)·...
(N > 0 — параметр целого типа; последний сомножитель в произведении равен 2, если N — четное число, и 1, если N — нечетное). С помощью этой функции вычислить двойные факториалы пяти данных чисел.

Double Fact2(int N)

{
if(N <= 1)
return 1;
If(N == 2)
return 2;
return N * Fact2(N – 2);
}

Recur4. Описать рекурсивную функцию Fib1(N) целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число):
F₁ = F₂ = 1, F_K = F_K−2 + F_K−1, K = 3, 4, ... . С помощью этой функции найти пять чисел Фибоначчи с данными номерами, и вывести эти числа вместе с количеством рекурсивных вызовов функции Fib1, потребовавшихся для их нахождения.

#include

using namespace std;
int FibRec(int N, int& count){
++count;
if (N == 1 || N == 2) return 1;
return FibRec(N - 1, count) + FibRec(N - 2, count);
}
int main(){
int m[5];
cout << "Enter 5 numbers: ";
for (int i = 0; i < 5; ++i){
cin >> m[i];
}
for (int i = 0; i < 5; ++i){
int count = 0;
cout <<"Fib" << m[i] << " = "<< FibRec(m[i], count);
cout << ", number of function calls: " << count << endl;
}
cout << endl;
system("pause");
}