Лабораторная работа 3.3. Рекурсивные функции

Цель. Научиться создавать рекурсивные функции. Понять отличия между рекурсивными и итеративными функциями.

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 1. Создайте рекурсивную и итеративную функцию, которая принимает в качестве аргумента число и возвращает его факториал.

#include <iostream>

using namespace std;

int fact_rec(int n) {

if (n==0) {

return 1;

} else {

return n*fact_rec(n-1);

}

}

int fact(int n) {

int result=1;

for (int i=1; i<=n; i++) {

result*=i;

}

return result;

}

int main() {

cout << fact_rec(3) << endl;

cout << fact(3) << endl;

cout << fact_rec(7) << endl;

cout << fact(7) << endl;

system("pause");

return 0;

}

Задача 2. Создайте рекурсивную и итеративную процедуру, которая принимает в качестве аргумента число и выводит все четные числа из диапазона от 1 до этого числа.

#include <iostream>

using namespace std;

void evens_rec(int n) {

if (n>1) {

evens_rec(n-1);

if (n%2==0) {

cout << " " << n;

}

}

}

void evens(int n) {

for (int i=1; i<=n; i++) {

if (i%2==0) {

cout << " " << i;

}

}

}

int main() {

evens_rec(100);

cout << endl;

evens(100);

cout << endl;

system("pause");

return 0;

}

Задача 3. Создайте рекурсивную и итеративную функцию, которая принимает два целочисленных аргумента и возвращает их наибольший общий делитель. Используйте алгоритм Евклида, основанный на том, что НОД(a,b)=НОД(a,b mod a).

#include <iostream>

using namespace std;

int nod_rec(int a, int b) {

int min = a<b? a: b;

int max = a>b? a: b;

if (min==0) {

return max;

} else {

return nod_rec(min, max%min);

}

}

int nod(int a, int b) {

int min = a<b? a: b;

int max = a>b? a: b;

while (min>0) {

int temp = max%min;

max=min;

min=temp;

}

return max;

}

int main() {

cout << nod_rec(100, 202) << endl;

cout << nod(100, 202) << endl;

system("pause");

return 0;

}

Задача 4. Создайте рекурсивную и итеративную функцию, которая принимает в качестве аргумента число и возвращает количество единиц в десятичной записи этого числа.

#include <iostream>

using namespace std;

int ones_rec(int n) {

if (n<10) {

return n==1;

}

if (n>=10) {

if (n%10==1) {

return 1+ones_rec(n/10);

} else {

return ones_rec(n/10);

}

}

}

int ones(int n) {

int t=n;

int result=0;

while(t>0) {

if (t%10==1) {

result++;

}

t/=10;

}

return result;

}

int main() {

cout << ones_rec(222) << endl;

cout << ones_rec(15123) << endl;

cout << ones(222) << endl;

cout << ones(15123) << endl;

system("pause");

return 0;

}

Задача 5. Создайте рекурсивную и итеративную функцию, которая принимает в качестве аргумента целое число и возвращает элемент последовательности, полученной с помощью мультипликативного линейного конгруэнтного генератора, номер которого равен этому числу. Воспользуйтесь рекуррентным соотношением x_n=a*x_n-1.

#include <iostream>

using namespace std;

int mlcg_rec(int n) {

int x0=23, a=10, m=12345;

if (n==0) {

return x0;

} else {

return (a*mlcg_rec(n-1))%m;

}

}

int mlcg(int n) {

int x0=23, a=10, m=12345;

int result=x0;

for (int i=0; i<n; i++) {

result = a*result%m;

}

return result;

}

int main() {

for (int i=0; i<50; i++) {

cout<<mlcg_rec(i)<<" "<<mlcg(i)<<endl;

}

system("pause");

return 0;

}

ЗАДАЧИ

Во всех задачах данной темы требуется создать рекурсивную и итеративную реализацию функции (процедуры).

1. Создайте процедуру, которая принимает число N и выводит числа от 1 до N. Воспользуйтесь рекуррентным соотношением. Вывести(1…N) = Вывести(1…N-1) и Вывести(N).

2. Создайте процедуру, которая принимает число N и выводит числа от N до 1. Вывести(N…1) = Вывести(N) и Вывести(N-1…1).

3. Создайте процедуру, которая принимает в качестве аргумента число N и выводит на экран N звездочек. Воспользуйтесь рекуррентным соотношением Вывести(N звездочек) = Вывести(N-1 звездочку) и Вывести(1 звездочку).

4. Создайте процедуру, которая принимает в качестве аргумента число N и выводит все четные числа из диапазона от 1 до N. Воспользуйтесь рекуррентным соотношением: Вывести(1…N) = Вывести(1…N-1), и, Если N-четное, то Вывести(N).

5. Создайте процедуру, которая принимает в качестве аргумента число N и выводит все нечетные числа из диапазона от 1 до N. Воспользуйтесь рекуррентным соотношением: Вывести(1…N) = Вывести(1…N-1), и, Если N-нечетное, то Вывести(N).

6. Создайте процедуру, которая принимает в качестве аргумента число N и выводит числа из диапазона от -N до N. Воспользуйтесь рекуррентным соотношением: Вывести(-N…N) = Вывести(N), Вывести(N-1…N-1), Вывести(N).

7. Создайте процедуру, которая принимает в качестве аргумента число N и выводит все четные числа из диапазона от 1 до N. Воспользуйтесь рекуррентным соотношением: Вывести(1…N) = Вывести(1…N-1) и Если N-четное, то Вывести(N).

8. Создайте функцию, которая принимает натуральное число в качестве аргумента и возвращает факториал этого числа. Воспользуйтесь рекуррентным соотношением N! = (N-1)!*N.

9. Создайте функцию, которая принимает в качестве аргумента натуральное число N и возвращает значение элемента последовательности Фибоначчи с таким номером. Воспользуйтесь рекуррентным соотношением f_n = f_n-1+f_n-2.

10. Создайте функцию, которая принимает два целочисленных аргумента и возвращает их наибольший общий делитель. Используйте алгоритм Евклида, основанный на том, что НОД(a,b)=НОД(a,b mod a).

11. Создайте функцию, которая принимает в качестве аргумента число n и возвращает сумму целых чисел от 1 до n.

12. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает элемент последовательности, полученной с помощью линейного конгруэнтного генератора, номер которого равен этому числу. Воспользуйтесь рекуррентным соотношением x_n=a*x_n-1+b.

13. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает элемент последовательности, полученной с помощью мультипликативного линейного конгруэнтного генератора, номер которого равен этому числу. Воспользуйтесь рекуррентным соотношением x_n=a*x_n-1.

14. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает 2 в степени, равной этому числу. Воспользуйтесь рекуррентным соотношением 2ⁿ=2*2^n-1.

15. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает число Люка с таким номером. Воспользуйтесь рекуррентным соотношением x_n=x_n-1+x_n-2.

16. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает значение элемента последовательности Трибоначчи с таким номером. Используйте рекуррентное соотношение x_n=x_n-1+x_n-2+x_n-3.

17. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает сумму цифр этого числа. Воспользуйтесь рекуррентным соотношением f(x)=f(x/10) + (x mod 10).

18. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает количество пятерок в десятичной записи этого числа. Воспользуйтесь рекуррентным соотношением f(x)=f(x/10) + t, где t=1, если x mod 10 = 5 и t=0 иначе.

19. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает его вес Хэмминга. Воспользуйтесь рекуррентным соотношением h(x)=h(x/2) + (x mod 2).

20. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает количество цифр в этом числе. Воспользуйтесь рекуррентным соотношением f(x)=f(x/10) + 1.

21. Создайте функцию, которая принимает в качестве аргументов целые числа x и y, а возвращает x^y. Воспользуйтесь рекуррентным соотношением x^y=x*x^y-1.

22. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает строку, являющуюся двоичным представлением этого числа. Воспользуйтесь рекуррентным соотношением f(x)=f(x/2) + «1» (или «0»).

23. Создайте функцию, которая принимает в качестве аргумента номер элемента арифметической прогрессии и возвращает значение этого элемента при _x0=3.1 и d=2.3. Воспользуйтесь рекуррентным соотношением _xn=_xn-1+d.

24. Создайте функцию, которая принимает в качестве аргумента номер элемента геометрической прогрессии и возвращает значение этого элемента при x₀=5.3 и q=1.3. Воспользуйтесь рекуррентным соотношением x_n=x_n-1*q.

25. Создайте функцию, которая принимает в качестве аргумента номер псевдослучайного числа, полученного при помощи генератора BBS, и возвращает это число x₀=20 и m=1081. Воспользуйтесь рекуррентным соотношением x_n = (x_n-1)² mod m.

26. Создайте функцию, которая принимает в качестве аргумента номер псевдослучайного числа, полученного при помощи генератора Фибоначчи, и возвращает это число при x₀=20, x₁=51 и m=501. Воспользуйтесь рекуррентным соотношением: x_n = (x_n-1 + x_n-2) mod m.

27. Создайте функцию, которая принимает в качестве аргумента целое число N и вычисляет сумму S(N)=1²+2²+3²+…+N². Воспользуйтесь рекуррентным соотношением S(N)=S(N-1)+N².

28. Создайте функцию, которая принимает в качестве аргумента целое число N и вычисляет сумму S(N)=1/1+1/2+1/3+…+1/N. Воспользуйтесь рекуррентным соотношением S(N)=S(N-1)+1/N.

29. Создайте функцию, которая принимает в качестве аргументов два целых неотрицательных числа и возвращает их вес Хэмминга. Тестовые примеры: hd(15,15)=0, hd(14,13)=2, hd(14,12)=1, hd(14,11)=2, hd(14,10)=1.

30. Создайте функцию, которая принимает в качестве аргумента целое число и возвращает его цифровой корень.