Пример 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;

}

Дата добавления: 2014-01-07