Пример 4. Построение дерева
Пример 5. Рекурсивный узор
Пример 3. Нахождение НОДа
Пример 2. Вычисление факториала
Пример 1.
Рекурсия
Рекурсия относится к одному из фундаментальных понятий в математических и компьютерных науках. В языках программирования рекурсивной программой называют программу, которая обращается к самой себе. Рекурсивная программа не может вызывать себя до бесконечности, поскольку в этом случае она никогда не завершилась бы. Вторая важная особенность рекурсивной программы — наличие условия завершения, позволяющего программе прекратить вызывать себя.
Рекурсия бывает:
- Прямая . Когда функция вызывает сама себя из своего же тела. Например:
void func()
{
func();
}
- Косвенная. Когда функция вызывается из другой функции, вызов которой происходит из начальной функции. Например
void func()
{
tmp();
}
void tmp()
{
func();
}
Примеры использования рекурсии:
void print (int p)
{
if(p== 0) return;
printf ("%i", p);
print (p-1);
}
void main()
{
print();
}
int fact(int k)
{
if(k== 1) return 1;
else return k*fact(k-1);
}
void main ()
{
printf("%i",fact(3));
}
#include<conio.h>
#include<stdio.h>
int nod(int n, int m)
{
if (n==m) return m;
if (n>m) nod(n-m, m);
else nod(n, m-n);
}
//__________________________________________
void main()
{
clrscr();
int n=8, m=12;
printf("%i",nod(n,m));
}
Пример 4. Нахождение макс. элемента
Во множестве рекурсивных алгоритмах используется два рекурсивных вызова, каждый из которых работает приблизительно с половиной входных данных. Эта рекурсивная схема — один из более важных случаев хорошо известного метода "разделяй и властвуй". Давайте в качестве примера рассмотрим задачу отыскания максимального из N элементов, сохраненных в массиве а[0], ..., a[N-l]. Эту задачу можно легко выполнить за один проход массива демонстрируется в примере:
int t;
for (t = a[0], i = 1; i < N; i++)
if (a[i] > t ) t= a[i] ;
Еще один простой алгоритм решения той же задачи использует рекурсию только с целью иллюстрации концепции "разделяй и властвуй".
int t;
int findmax (int arr[], int l, int r)
{
if (l == r) return a[0];
int m = (l+r)/2;
int u = findmax (arr, l, m) ;
int v = findmax (arr, m+1, r) ;
if (u > v) return u; else return v;
}
#include <graphics.h>
#include <conio.h>
#include <dos.h>
#include <math.h>
#include <stdlib.h>
void uzor(int x, int y, int r, int p)
{
circle (x,y,z); // x,y - координаты центра
// r - радиус, p - текущий уровень вложенности
if(p>0)
{
uzor(x,y-r,r/4,p-1);
uzor(x-r,y,r/4,p-1);
uzor(x,y+r,r/4,p-1);
uzor(x+r,y,r/4,p-1);
}
}
void main()
{
int gdrive = DETECT, gmode;
initgraph(&gdrive,&gmode,"C:\\Lang\bc32\\BGI");
uzor(320,240,100,55);
Outtextxy(10,460,"press any key");
getch();
closegraph();
}
#include <graphics.h>
#include <conio.h>
#include <dos.h>
#include <math.h>
#include <stdlib.h>
int branch = 4; // количество веток в кусте
int branch_len = 70;
double alpha; // угол между ветками
void drawTree (int p, int ox, int oy, int len, double angle)
{
// p - уровень куста
if(p<1) return;
double beta = angle;
int px,py; // координаты конца ветки
for(int i=0, i<branch, i++)
{
beta+=alpha;
if(random(100)<75)
{
px = ox+(len*cos(beta))*1,3;
py = oy-(len*sin(beta))*1;
lime(ox,oy,px,py);
drawTree(p-1,px,py,len*0,75,beta-MPI_2);
}
}
}
void main()
{
//переход в графический режим
randomize();
int cx,cy,mx,my,sx,sy;
mx = getmaxx();
my = getmaxy();
cx = mx/2;
cy = my/2
sx = cx;
sy = cy*1.5;
line(mx,my,sx,sy);
alpha = M_PI/(branch+1);
drawTree(7,sx,sy,br_len,0);
getch();
close graph;
}