Рекурсия

← →
Николай Быков © (2002-10-11 14:38) [0]

Я понял рекурсию на примере функции по вычислению факториала. Но когда начал решать задачки на использование рекурсии, то у меня ничего не получилось. Не могли бы вы мне объяснить рекурсию не на примере факториала?

← →
han_malign © (2002-10-11 14:43) [1]

выложи что у тебя не получилось, а тебе объяснят почему, так быстрее поймешь

← →
Skier © (2002-10-11 14:44) [2]

>Николай Быков
Самое главное в этом деле - должна быть "затычка",
т.е. условие возврата из рекурсии...
Иначе Stack Overflow - гарантируется !

← →
qube © (2002-10-11 14:45) [3]

Ну, допустим, обход дерева.

type PMyTreeNode = ^TMyTreeNode; TMyTreeNode = record left, right: PMyTreeNode; data: integer; end; procedure PrintTree(Root: TMyTreeNode); begin writeln(data); PrintTree(left^); PrintTree(right^); end;

т.е., естественно использовать рекурсию при обработке данных, по природе рекурсивных.

← →
Николай Быков © (2002-10-11 14:45) [4]

>Николай Быков © (11.10.02 14:38)
> объяснить рекурсию

← →
Николай Быков © (2002-10-11 14:47) [5]

2 куб
Я с деревьями не знаком. Может по проще
У меня конкретно не олучались задачи:
н член арифметической/геометрической прогрессии, перевод из DEC в BIN

← →
Дремучий © (2002-10-11 14:48) [6]

1.Возьми деньги в тумбочке
2.Пересчитай, если мало - скажи мне
3.Если ты мне скажешь - я положу деньги в тумбочку
4.Если не скажешь - иди в магазин, купи пива
5.Если денег на пиво не хватает - возьми деньги в тумбочке
cм. п.1.

:))

← →
Skier © (2002-10-11 14:48) [7]

>Николай Быков

> объяснить рекурсию

Это когда функция вызывает сама себя.
(Проще некуда...)<

← →
qube © (2002-10-11 14:50) [8]

Ой, соврал.
procedure PrintTree(Root: TMyTreeNode);
begin
if Root = nil then Exit;
writeln(data);
PrintTree(left^);
PrintTree(right^);
end;

← →
Alx2 © (2002-10-11 14:50) [9]

>Николай Быков © (11.10.02 14:38)

На примере чисел Фибоначчи можно? :)

Рекурсия - косвенный или прямой вызов процедурой или функции самой себя. Например - рисуешь кусты. Из чего это состоит? Схематично - из веток наподобие куриной лапы с большими пальцами врастопырку.
Пишем процедуру, рисующую одну лапу, наклоненную под определенным углом "к горизонту" и расположенной в определенном месте окна. А потом рисуем остальные лапы - для этого достаточно рисующей процедуре вызвать смою себя с другими параметрами для каждого пальца уже нарисованной лапы(параметры скажут процедуре, что лапа должна быть поменьше, расти из пальца предыдущей лапы, наклонена перпендикулярно к пальцу). После отрисовки лапы поменьше произойдет еще один вызов ее из самой себя дл отрисовки еще менньшего пальца и.т.д до определенной "пушистости". Таким образом будет весьма кустистый пейзаж :)

← →
Странник © (2002-10-11 14:58) [10]

...
при переходе от одной матрицы параметров описывающей "куст" к другой с некоторым коеффициентом получаем т.н. фрактальный морфинг. Примеры фрактального морфинга наблюдаются ежедневно в телевизоре - перетекание одного изображения в другое, самый запоминающийся пример - терминатор из "жидкого" металла в "Терминатор-2" - сплошная рекурсия. ;-)).
При использовании рекурсивных процедур, в обязательном порядке д.б. учтено требование реентерабельности.

← →
Николай Быков © (2002-10-11 14:59) [11]

Ну вот я честно списал решение задачи на рекурсию
function geompr(b1,q,n:integer):integer; begin if n=1 then geompr:=b1 else geompr:=geompr(b1,q,n-1)*q; end;
вычисляет н член геом прогрессии

← →
kaif © (2002-10-11 14:59) [12]

Общий принцип рекурсивного вызова в том, что, когда функция вызывает сама себя, образуется как бы еще один ее "экземпляр". На деле сначала создаются все экземляры, а потом это все начинает завершаться. Чтобы не возникло переполнения стека нужно, чтобы вызов происходил при определенном условии:
--------------------
procedure AAA;
begin
AAA;
end; // это будет вечный вызов и переполнение стека.
-----------------------
procedure BBB;
begin
if <условие> then
BBB;
end; // это в принципе можно завершить.
----------------------
Ну и нежелательно, чтобы число экземляров достигало миллионов.
----------------------

← →
vuk © (2002-10-11 15:05) [13]

to Alx2:
Типичный фрактальный алгоритм. :o)

← →
Николай Быков © (2002-10-11 15:06) [14]

2 Алкс2
Я не знаю что такое фракталы

← →
Alx2 © (2002-10-11 15:13) [15]

>vuk © (11.10.02 15:05)
Конечно.
Но зачем же сразу страшными словами? :))

← →
vuk © (2002-10-11 15:13) [16]

В общем случае фракталы - математические объекты для которых характерно самоподобие. То есть часть объекта подобна объекту целиком. В принципе, визуализированные фрактлы зачастую имеют весьма причудливую форму и при этом задаются весьма простыми законами образования.

← →
Николай Быков © (2002-10-11 15:14) [17]

А может все таки на простом примере объясните. Я вам даже написал его.

← →
han_malign © (2002-10-11 15:15) [18]

если на пальцах - более мелкий элемент фрактала повторяет вид большого

\/ \/ \/ \/
\ / \ /
\/ \/
\ /
\ /
\ /
\/

← →
Николай Быков © (2002-10-11 15:18) [19]

ДА я даже не собираюсь понимать фракталы. Я и так загружен рекурсией, а тут еще и вы. Ну трудно что ли на примере, который я дал объяснить?

← →
Johnny Smith © (2002-10-11 15:30) [20]

Николай Быков © (11.10.02 15:18)
ДА я даже не собираюсь понимать фракталы. Я и так загружен рекурсией, а тут еще и вы. Ну трудно что ли на примере, который я дал объяснить?
2All
Да, блин! Хватит малыша умными словами пичкать!
Фракталы тут развели, понимаешь! Вы еще ему про гипотермию пениса расскажите. Не знаете, что ли, что последует?
:)))))))

← →
Николай Быков © (2002-10-11 15:31) [21]

Не надо переходить в треп. Помогите понять рекрсию на написанном мною примере

← →
Mike Kouzmine (2002-10-11 15:33) [22]

Пример некорректен. Изначально. Неверно сделано. Нужен контейнер, т.е. список.
type
PMyTreeNode = ^TMyTreeNode;
TMyTreeNode = record
Вершина : PMyTreeNode;
left, right: PMyTreeNode;
data: integer;
end;

Нужна вершина дерева, то бишь начало списка, он в контейнере.
procedure PrintTree(Root: TMyTreeNode);
procedure Print(R: TMyTreeNode);
begin
if R.Left <> Nil then Print(R.Left);
WriteLn(R.Data);
end;
begin
Print(Root.Вершина);
end;

← →
Кулюкин Олег © (2002-10-11 15:33) [23]

А Яндекс отказывается искать слово рекурсия???

← →
MBo © (2002-10-11 15:35) [24]

вынесем b1 и й для простоты во внешние переменные
function g(n:integer):integer;
begin
if n>1 then g:=q*g(n-1)
else
g:=b1;
end;

пусть вызвали с n=3
получается
a) g:=q*g(2) - вызов с n=2
b) g:=q*g(1) - вызов с n=1
c) g:=b1 - стоп, возвращаемся в пред. вызов
b) g:=q*b1 (g, полученное в пред. строке)
a) g:=q*(q*b1) (g, полученное в пред. строке)
все, функция возвращает результат - b1*q^2

← →
Mike Kouzmine (2002-10-11 15:36) [25]

Пардон
procedure PrintTree(Root: TMyTreeNode);
procedure Print(R: TMyTreeNode);
begin
if R.Left <> Nil then
begin
Print(R.Left);
WriteLn(R.Data);
end;
end;
begin
Print(Root.Вершина);
end;

← →
Digitman © (2002-10-11 15:36) [26]

>Johnny Smith

А далее последует "Эй, пипл, набираю в DiamondSoft учиться рекурсии !"

Подпись : непринятый в DiamondSoft и посему страшно обиженный пипл-item))))

← →
Николай Быков © (2002-10-11 15:41) [27]

2 МБо
То есть сначала все расписывается в памяти пока не дойдет до условия возврата из функции, а потом с конца к началу все выполняется? Я правильно понял?

← →
Alx2 © (2002-10-11 15:41) [28]

А вот кустик кому? Кому кустик зелененький? :))

procedure TForm1.FormPaint(Sender: TObject); Const MaxCount=10; procedure PaintBush(counter, x1,y1 : Integer; len : double; angle : double=Pi/2); Var np : TPoint; begin if counter<=0 then exit; dec(counter); Canvas.MoveTo(x1,y1); Canvas.Pen.Color := RGB(0,(MaxCount-counter)*10,0); np := point(x1+round(len*cos(angle)),y1-round(len*sin(angle))); Canvas.LineTo(np.X,np.Y); PaintBush(counter,np.X,np.y, len/(1+random*1.2), angle-Pi/5); PaintBush(counter,np.X,np.y, len/(1+random*1.2), angle); PaintBush(counter,np.X,np.y, len/(1+random*1.2), angle+Pi/5); end; begin randomize; PaintBush(MaxCount,ClientWidth div 2,ClientHeight, ClientHeight div 5); end;

← →
qube © (2002-10-11 15:42) [29]

Mike Kouzmine (11.10.02 15:36)
Смотрел-смотрел, так и не понял, что в моем примере (с учетом поправки) неправильно. Нормальное бинарное дерево. Может, объясните?

← →
Pumpkin (2002-10-11 15:47) [30]

Хороший пример рекурсии - это "Как мне найти все файлы на диске?"
Посмотри в ФАК.
Выполнимость условия возврата - конечность глубины вложенности папок на диске.

← →
Mike B. © (2002-10-11 15:49) [31]

Помогите ему с суицидом - не придется объяснять про рекурсию

← →
Mike Kouzmine (2002-10-11 15:49) [32]

qube © -> У рекурсии должно быть начало и конец, как и у всех нас. Как ты ее определишь? У тебя в получается две ветки, причем каждая имеет свое условия для окончания вызовов. Первое условие - Root.Left = Nil, второе, как ты, наверное догадался Root.Right = Nil. Как ты поступишь?

>Николай Быков © (11.10.02 15:41)
>2 МБо
>То есть сначала все расписывается в памяти пока не дойдет до >условия возврата из функции, а потом с конца к началу все >выполняется? Я правильно понял?
Да, правильно. Рекурсия сначала порождает все экземляры, а потом это все вычисляется в обратном порядке. Вот только я бы еще поставил еще какое-то ограничение, чтобы не было переполнения стека или арифметического переполнения (что в данном случае вероятнее)...

function geompr(b1,q,n:integer):integer;
begin
if n=1 then geompr:=b1
else geompr:=geompr(b1,q,n-1)*q;
end;
b[n+1] = b[n]·q
каждый член последовательности (начиная со второго) равен предыдущему, умноженному на одно и то же число (знаменатель прогрессии)

Пусть b1=3 q=2 n=4, т.е. geompr(3,2,4)
4=1? - нет, тогда result=geompr(3,2,3)*4
3=1? - нет, тогда result=geompr(3,2,2)*3*4
2=1? - нет, тогда result=geompr(3,2,1)*2*3*4
1=1? - да, тогда result=3*2*3*4

qube © (11.10.02 14:50)

Ой, соврал.
procedure PrintTree(Root: TMyTreeNode);
begin
if Root = nil then Exit;
writeln(data);
PrintTree(left^);
PrintTree(right^);
end;

2 РВ
При проверке
> 1=1? - да, тогда result=3*2*3*4

Получается, что geompr присваивается b1, которое равно 3

нет, предыдущие накопления тащаться

← →
Mike Kouzmine (2002-10-11 16:00) [38]

qube © (11.10.02 14:50)

Ой, соврал.
procedure PrintTree(Root: TMyTreeNode);
begin
if Root = nil then Exit;
writeln(data);
PrintTree(left^);
PrintTree(right^);
end;
Теперь правильно - сначала печатает себя, потом левую ветку, потом правую.

Mike Kouzmine (11.10.02 16:00)
Ну так, чего ж ругаешь? :) Неправильно, изначально. Абыдные слова гаваришь, да?

Поправку-то я раньше внес, чем ты критиковать начал.

Хотя на самом деле неправильно.
writeln(Root.data); //теперь совсем правильно

← →
Mike Kouzmine (2002-10-11 16:08) [40]

Это не суть, важен принцип

Короче на пальцах про рекурсию

function geompr1(b1,q,n:integer):integer; begin if n=1 then geompr1:=b1 else geompr1:=geompr2(b1,q,n-1)*q; end; function geompr2(b1,q,n:integer):integer; begin if n=1 then geompr2:=b1 else geompr2:=geompr3(b1,q,n-1)*q; end; ......................................... function geomprN(b1,q,n:integer):integer; begin if n=1 then geomprN:=b1;//однозначно N=n end;
просто при рекурсии, вместо других экземпляров функции, используется тот же физический фрагмент кода

Хороший пример бесконечной рекурсии это
"У попа была собака ..."

Например:
Дракон Хартера-Хейтуэя

function K(I:Integer):Integer; begin if i mod 2=0 then k:=K(i div 2) else K:=i mod 4; end; procedure TForm1.FormPaint(Sender: TObject); var x,y,i,Step,angle:Integer; begin Step:=1; angle:=0; x:=width div 2; y:=height div 2; canvas.Pen.Color:=0; canvas.MoveTo(x,y); for i:=1 to 100000000 do begin angle:=(angle+K(i)*90) mod 360; if angle=0 then y:=y-step; if angle=90 then x:=x-step; if angle=180 then y:=y+step; if angle=270 then x:=x+step; canvas.LineTo(x,y); end; end;

Рекурсия Найти похожие ветки