6.4 Рекурсии
Рекурсивная функция – это функция, которая вызывает сама себя либо непосредственно, либо косвенно с помощью другой функции.
Пример 6.3
Написать рекурсивную функцию поиска наибольшего общего делителя.
/************************************************/
/* Функции. Рекурсии. */
/* Написать рекурсивную функцию */
/* нахождения НОД двух чисел. */
/************************************************/
#include <stdio.h>
#include <conio.h>
void NOD(int,int);
// Функция вычисления НОД двух чисел
void NOD(int a,int b)
{
if (a>b) a=a-b;
else b=b-a;
if (b==0)
{
printf("\n \t NOD двух чисел равен %d",a);
return;
}
NOD(a,b);
}
// Основная программа
void main()
{
clrscr();
int k,l;
printf("\t Введите два числа: ");
scanf("%d %d",&k,&l);
NOD(k,l); // вызов функции
getch();
}
Результат работы программы.
Введите два числа: 8 12
NOD двух чисел равен 4
Пример 6.4
Написать рекурсивную функцию двоичного поиска по ключу в упорядоченном массиве.
/************************************************/
/* Функции. Рекурсии. */
/* Написать рекурсивную функцию */
/* двоичного поиска по ключу в */
/* упорядоченном массиве. */
/************************************************/
#include <stdio.h>
#include <conio.h>
#define size 50
int bisearch(int a[],int key, int &li, int &rj);
void main()
{
clrscr();
int x[size];
int n,ind,key,a,b;
// Ввод и вывод массива
printf(" Введите число элементов массива: \n");
scanf("%d", &n);
printf(" Введите массив: \n");
for(int i=0; i<n; i++)
scanf("%d",&x[i]);
for(i=0; i<n; i++)
printf(" %d",x[i]);
printf(" Введите ключ: \n");
scanf("%d", &key);
a=0;
b=n-1;
ind= bisearch(x,key,a,b); // вызов функции
if(ind > -1)
printf("\n Ключ найден: %d",x[ind]);
else
printf("\n Такого элемента нет в массиве\n");
getch();
}
int bisearch(int a[],int key, int &li, int &rj)
{
int k;
if(li<=rj)
{
k=(li+rj)/2;
printf("\n k=%d",k);
if(key > a[k])
{
li=k+1;
return(bisearch(a,key, li,rj));
}
else
if (key<a[k])
{
rj=k-1;
return(bisearch(a,key, li,rj));
}
else
{
printf("\n a[k]=%d", a[k]);
return k;
}
}
k=-1;
return k;
}
Результат работы программы.
Введите число элементов массива:
10
Введите массив:
4 6 9 12 16 18 22 28 34 40
4 6 9 12 16 18 22 28 34 40
Введите ключ: 18
k=4
k=7
k=5
a[k]=18
Ключ найден: 18
6.4.1 Для заданных границ интегрирования a и b вычислить значение определенного интеграла следующего вида:
№ |
Интеграл |
1. |
|
2. |
|
3. |
|
4. |
|
5. |
|
6. |
|
7. |
|
8. |
|
9. |
|
10. |
|
11. |
|
12 |
|
13 |
|
14. |
|
15. |
|
16. |
|
17. |
|
18. |
|
19. |
|
20. |
|
21. |
|
22. |
|
23. |
|
24. |
|
25. |
|
