Как выйти из рекурсии

← →
Andy BitOff © (2009-03-18 12:12) [0]

Как быстро выйти из глубокой рекурсии на первый уровень?

← →
Palladin © (2009-03-18 12:16) [1]

первый уровень должен знать, что он первый уровень, остальные - знать, что они не первый. и волшебное слово exit все решает.

← →
KSergey © (2009-03-18 12:17) [2]

raise exception

← →
oxffff © (2009-03-18 12:19) [3]

> Andy BitOff © (18.03.09 12:12)
> Как быстро выйти из глубокой рекурсии на первый уровень?
>

Нужно код показать.

← →
Palladin © (2009-03-18 12:25) [4]

> KSergey © (18.03.09 12:17) [2]

и вылетишь ты из всех уровней...

← →
Slym © (2009-03-18 12:33) [5]

мега pop"нуть :)

← →
Ega23 © (2009-03-18 12:36) [6]

> и вылетишь ты из всех уровней...
>

Да ладно?

← →
Palladin © (2009-03-18 12:39) [7]

> Ega23 © (18.03.09 12:36) [6]

Да. Ладно.

← →
Andy BitOff © (2009-03-18 12:46) [8]

procedure PassingPixel(x, y: integer); var i: integer; aRect: TRect; begin aRect := Rect(0, 0, qSource1.Width, qSource1.Height); qDest.SetPixel(x, y, clBlack); if DrawPixel(x, y + 1) then PassingPixel(x, y + 1); if DrawPixel(x + 1, y + 1) then PassingPixel(x + 1, y + 1); if DrawPixel(x + 1, y) then PassingPixel(x + 1, y); if DrawPixel(x + 1, y - 1) then PassingPixel(x + 1, y - 1); if DrawPixel(x, y - 1) then PassingPixel(x, y - 1); if DrawPixel(x - 1, y - 1) then PassingPixel(x - 1, y - 1); if DrawPixel(x - 1, y) then PassingPixel(x - 1, y); if DrawPixel(x - 1, y + 1) then PassingPixel(x - 1, y + 1); end;
Переопределение адреса стека не катит? Как в ассме.

> Palladin © (18.03.09 12:16) [1]

Да, я думал об этом. Это был перевый вариант, который пришел в голову, но потребуется две/три доп. переменные и дополнительные проверки.
Я просто думал, что побыстрее способ есть, который я не знаю. Такой как описал выше, например.

← →
Skyle © (2009-03-18 13:06) [9]

> Andy BitOff © (18.03.09 12:46) [8]
> но потребуется две/три доп. переменные

Есть мнение, что потребуется один параметр. Навскидку

← →
Сергей М. © (2009-03-18 13:13) [10]

//вход в рекурсию try PassingPixel(..); exсept end; procedure PassingPixel(x, y: integer); .. begin .. if SomeCondition then raise ESomeException.Create(..); .. end;

Так устроит ?

← →
KSergey © (2009-03-18 13:14) [11]

> Palladin © (18.03.09 12:25) [4]
> и вылетишь ты из всех уровней...

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

А вообще у меня сильное сомнение в эффективности приведенного кода. Рекурсия - штука красивая, да, но слишком затратная, особенно если только она и присутствует, как здесь.

← →
Кто б сомневался © (2009-03-18 13:15) [12]

> Как быстро выйти из глубокой рекурсии на первый уровень?

Неужто рекурсия настолько глубока, что break на всех уровнях займет больше секунды?

← →
KSergey © (2009-03-18 13:17) [13]

> Кто б сомневался © (18.03.09 13:15) [12]
> Неужто рекурсия настолько глубока, что break на всех уровнях займет больше секунды?

это какой-то размер стека нужен для секунды...

← →
PEAKTOP © (2009-03-18 13:20) [14]

> Andy BitOff © (18.03.09 12:12)
>
> Как быстро выйти из глубокой рекурсии на первый уровень?

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

Во вторых, - бросать надо это гиблое дело, батенька...

:)

← →
Andy BitOff © (2009-03-18 13:41) [15]

> Сергей М. © (18.03.09 13:13) [10]
> Так устроит ?

Только в крайнем случае, т.к. выход ИЗ рекурсии, а надо вернуться на первую итерацию. Т.е., если мы вошли в рекурсию и на первом же условии "if DrawPixel(x, y + 1) then PassingPixel(x, y + 1);" ушли глубоко, то нужно выйти из этого "глубоко" на вторую проверку "if DrawPixel(x + 1, y + 1) then PassingPixel(x + 1, y + 1);".

← →
Empleado © (2009-03-18 13:50) [16]

Может добавить счетчик?
procedure PassingPixel(x, y: integer; var RecCounter: integer);
И Exit пока не 1.

← →
Сергей М. © (2009-03-18 14:22) [17]

> Andy BitOff © (18.03.09 13:41) [15]

Счетчик добавь, см. [16]

← →
euru © (2009-03-18 15:27) [18]

procedure PassingPixel(x, y: Integer); const Counter: Integer = 0; begin try inc(Counter); . . . if Counter > 1 then exit; finally dec(Counter); end; end;

← →
oxffff © (2009-03-18 16:16) [19]

Я бы рекомендовал сделать так

procedure Sample;
var CurrentContex:integer;
List:TList<integer>;
RestOfTOp:integer;
begin
List:=TList<integer>.create;

List.Add(1);
List.Add(2);
List.Add(3);
RestOfTOp:=List.Count;

while List.Count>0 do
begin
CurrentContex:=List.Items[0];
List.delete(0);
Form1.Memo1.Lines.Add(IntToStr(CurrentContex));
//Конечное условие выхода
if CurrentContex<30 then
begin
List.Insert(0,CurrentContex+12);
List.Insert(0,CurrentContex+11);
List.Insert(0,CurrentContex+10);
end
else
begin
//Вот он этот выход на первый уровень
dec(RestOfTOp);
List.DeleteRange(0,List.Count-RestOfTOp);
end;
end;
List.free;
end;

← →
oxffff © (2009-03-18 16:20) [20]

> oxffff © (18.03.09 16:16) [19]

RestOfTOp - это остаток кроны дерева первого уровня

← →
MBo © (2009-03-18 16:38) [21]

8-связный FloodFill можно делать и нерекурсивно

← →
Asteroid (2009-03-18 18:01) [22]

> MBo © (18.03.09 16:38) [21]
> 8-связный FloodFill можно делать и нерекурсивно

Поддерживаю :)
Самый быстрый выход из рекурсии - не использовать рекурсию.

> MBo © (18.03.09 16:38) [21]
> 8-связный FloodFill можно делать и нерекурсивно

Старая ветка:

TUser © (16.05.06 14:28) [11]

Оформи все это циклом. Не надо использовать рекурсию, там где не надо.

while true do begin
if DrawPixel(x, y + 1) then inc (y) else
if DrawPixel(x + 1, y) then inc (x) else
...
if ... then ... else
break;
end;

-----------

MBo © (16.05.06 14:47) [12]

>TUser © (16.05.06 14:28) [11]

Сэр, да вы закоренелый рекурсофоб! ;)

В выбранной парадигме без рекурсии, циклом, подобным приведенному, не обойти всю область с закоулками (ну или свой стек придется делать для возврата)

------------------

TUser © (16.05.06 14:52) [13]

Ой, я действителньо ерунду написал.

Halt - самый быстрый выход из рекурсии

>Старая ветка:
Думаешь, я помню подробности? ;)

А кстати, почему выбрано восьмисвязное заполнение - нужно проникать через состыкованные уголки?

> MBo © (18.03.09 21:26) [25]
> >Старая ветка:
> Думаешь, я помню подробности? ;)

Думаю нет ;) Тем более ветка от мая 2006 =)

> А кстати, почему выбрано восьмисвязное заполнение - нужно
> проникать через состыкованные уголки?

Ну, на этой реализации, думаю, что не обязательно. Это пока еще не ясно...

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

Это-то я понимаю. Я просто на данном этапе не знаю какой получится результат, надо посмотреть так и так.

> Andy BitOff © (19.03.09 12:16) [30]
> > oxffff © (18.03.09 22:40) [29]
> > [19] Смотрел?
>
> Смотрел. Но как-то но особо понял что к чему.

А под отладчиком по шагам?

Под отладчиком не смотрел. У меня D7

Как выйти из рекурсии Найти похожие ветки