Пример рекурсивной программы построения окружностей

Рекурсивная программа построения окружностей

Пример программы с использованием рекурсии

Рекурсивные программы, примеры

Рассмотрим математическую головоломку из книги Ж. Арсака «Программирование игр и головоломок».

Построим последовательность чисел следующим образом: возьмем целое число i>1. Следующий член последовательности равен i/2, если i четное, и 3 i+1, если i нечетное. Если i=1, то последовательность останавливается.

Математически конечность последовательности независимо от начального i не доказана, но на практике последовательность останавливается всегда.

Применение рекурсии позволило решить задачу без использования циклов, как в основной программе, так и в процедуре.

Программист разрабатывает программу, сводя исходную задачу к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме.

Для вычисления F( N) может понадобиться вычислить F( N-1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.

Алгоритм, который является своей собственной частью, называется рекурсивным. Часто в основе такого алгоритма лежит рекурсивное определение.

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

N! = ( N-1)!* N, если N=0, то N!= 1

Любое рекурсивное определение состоит из двух частей. Одна часть определяет понятие через него же, другая часть – через иные понятия.

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

2n= 2 n-1*2, если n=0, то 2 n= 1

Процедура является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие процедуры).

рис. 23 – рекурсивная процедура

Заметим, что при косвенном обращении все процедуры в цепочке – рекурсивные.

Program Arsac;

Var first: word;

Procedure posledov (i: word);

Begin

Writeln (i);

If i=1 then exit;

If odd(i) then posledov(3*i+1) else posledov(i div 2);

End;

Begin

Write (‘ введите первое значение ’); readln (first);

Posledov (first);

Readln ;

End.

Написать программу, строящую на экране изображение:

рис. 24 – Построение окружностей

Изображение строится по следующему правилу: строится окружность с заданным радиусом r. Затем на диаметрально противоположных точках окружности ( x- r и x+ r)строится вновь окружность меньшего радиуса ( r=3 r/5). Для каждой меньшей окружности на диаметрально противоположных точках вновь строится окружность меньшего радиуса, и т.д., пока радиус не уменьшится до 10.

program recurs;

uses graph;

var x,y,r,d,m:integer;

procedure ris(x,y,r:integer);

var i:integer;

begin

if r<10 then exit;

circle(x,y,r);

for i:=1 to 1000 do; { просто цикл задержки }

ris(x+r,y,r*3 div 5);

ris(x-r,y,r*3 div 5);

end ;

begin {начало основной программы}

d:=detect;

initgraph(d,m,'e:\bp\bgi');

x:=320;

y:=240;

r:=120;

ris(x,y,r);

readln ;

end.