Как выйти из рекурсии c
Рекурсия — это такая организация выполнения работы функции, при которой данная функция вызывает сама себя.
Рекурсия может быть прямой и косвенной.
В случае прямой рекурсии вызов функцией самой себя делается непосредственно в этой же функции:
Косвенная рекурсия создаётся за счёт вызова данной функции из какой-либо другой функции, которая сама вызывалась из данной функции. Например, схема может быть такой:
Как видим, в main() вызывается функция A() , которая вызывает B() , а та в свою очередь вызывает снова A() . Понятно, что цепочка подпрограмм между вызовами функции A() могла быть не из одной функции B() , а из большего количества разных функции.
Стандартом языка C++ рекурсивно может вызываться любая функция, кроме main(), а по стандарту языка C рекурсивно можно вызвать даже main() !
Практика показывает , что функцию main() в ряде систем разработки ( CodeBlocks , например) можно вызвать на любом языке (и на C, и на C++) :
1)Прямая рекурсия функции main() на языке C++:
using namespace std;
2)Косвенная рекурсия функции main() на языке C++:
using namespace std;
В обоих примерах на экране монитора достаточно долго будет выводится радостный текст
а затем произойдёт аварийное завершение программы из-за переполнения стека.
Не зависимо от того, какой вид рекурсии используется (прямая или косвенная), в рекурсивной функции обязательно должна выполняться проверка какого-либо условия, в зависимости от которого осуществлялся бы выход из рекурсивной функции . Причём, необходимо гарантировать, что это условие обязательно будет выполнено через конечное количество рекурсивных вызовов, и функция в конце концов закончит работу . Иначе — аварийное завершение, смотри примеры выше.
Последовательный вызов функцией самой себя называют рекурсивным спуском , последовательный выход из многократного вызова — рекурсивным подъёмом .
При каждом рекурсивном вызове функции заново выделяется память под локальные переменные.
Рассмотрим примеры
Пример 1 . Вычислить факториал n! .
Задача проста, но для понимания рекурсии вполне пригодна. По определению, n! — это произведение первых n натуральных чисел.
Если известен, к примеру, 4! , то 5! вычисляем по формуле: 5!=5·4! .
Воспользуемся этим фактом и получим следующую рекурсивную функцию (приведём весь текст программы):
Как выйти из рекурсии c
← →
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]
и вылетишь ты из всех уровней.
Да ладно?
← →
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]
> но потребуется две/три доп. переменные
Есть мнение, что потребуется один параметр. Навскидку
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;
RestOfTOp:integer;
begin
List:=TList.create;
while List.Count>0 do
begin
CurrentContex:=List.Items[0];
List.delete(0);
Form1.Memo1.Lines.Add(IntToStr(CurrentContex));
//Конечное условие выхода
if CurrentContex 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 можно делать и нерекурсивно
Поддерживаю 🙂
Самый быстрый выход из рекурсии — не использовать рекурсию.
← →
Andy BitOff © ( 2009-03-18 18:22 ) [23]
> 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]
Ой, я действителньо ерунду написал.
← →
clickmaker © ( 2009-03-18 18:26 ) [24]
Halt — самый быстрый выход из рекурсии
← →
MBo © ( 2009-03-18 21:26 ) [25]
>Старая ветка:
Думаешь, я помню подробности? 😉
А кстати, почему выбрано восьмисвязное заполнение — нужно проникать через состыкованные уголки?
← →
Andy BitOff © ( 2009-03-18 21:34 ) [26]
> MBo © (18.03.09 21:26) [25]
> >Старая ветка:
> Думаешь, я помню подробности? 😉
Думаю нет 😉 Тем более ветка от мая 2006 =)
> А кстати, почему выбрано восьмисвязное заполнение — нужно
> проникать через состыкованные уголки?
Ну, на этой реализации, думаю, что не обязательно. Это пока еще не ясно.
← →
MBo © ( 2009-03-18 21:39 ) [27]
Дело в том, что восьмисвязное может в нежелательные места залезть — например, пробраться сквозь наклонную однопиксельную линию. Так что использовать его стоит далеко не всегда.
← →
Andy BitOff © ( 2009-03-18 22:10 ) [28]
Это-то я понимаю. Я просто на данном этапе не знаю какой получится результат, надо посмотреть так и так.
← →
oxffff © ( 2009-03-18 22:40 ) [29]
> Andy BitOff © (18.03.09 22:10) [28]
[19] Смотрел?
← →
Andy BitOff © ( 2009-03-19 12:16 ) [30]
> oxffff © (18.03.09 22:40) [29]
> [19] Смотрел?
Смотрел. Но как-то но особо понял что к чему.
← →
oxffff © ( 2009-03-19 12:43 ) [31]
> Andy BitOff © (19.03.09 12:16) [30]
> > oxffff © (18.03.09 22:40) [29]
> > [19] Смотрел?
>
> Смотрел. Но как-то но особо понял что к чему.
А под отладчиком по шагам?
← →
Andy BitOff © ( 2009-03-19 13:48 ) [32]
Под отладчиком не смотрел. У меня D7
Как выйти из рекурсии c
Рекурсивные функции — это функции, которые вызывают сами себя. Такие функции довольно часто используются для обхода различных представлений. Например, если нам надо найти определенный файл в папке, то мы сначала смотрим все файлы в этой папке, затем смотрим все ее подпак
Например, определим вычисление факториала в виде рекурсивной функции:
#include unsigned long long factorial(unsigned); int main() < unsigned n ; auto result < factorial(n)>; std::cout unsigned long long factorial(unsigned n) < if(n >1) return n * factorial(n-1); return 1; >
В функции factorial задано условие, что если число n больше 1, то это число умножается на результат этой же функции, в которую в качестве параметра передается число n-1. То есть происходит рекурсивный спуск. И так далее, пока не дойдем того момента, когда значение параметра не будет равно 1. В этом случае функция возвратит 1.
Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и к которому сходится выполнение остальных вызовов этой функции. В случае с факториалом базовый вариант представлен ситуацией, при которой n = 1. В этом случае сработает инструкция return 1; .
Например, при вызове factorial(5) получится следующая цепь вызовов:
- 5 * factorial(4)
- 5 * 4 * factorial(3)
- 5 * 4 * 3 * factorial(2)
- 5 * 4 * 3 * 2 * factorial(1)
- 5 * 4 * 3 * 2 * 1
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фиббоначчи. n-й член последовательности чисел Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. Значения f(0)=0 и f(1)=1, таким образом, определяют базовые варианты для данной функции:
#include unsigned long long fib(unsigned); int main() < for(unsigned i<>; i < 10; i++) < auto n = fib(i); std::cout std::cout unsigned long long fib(unsigned n)
Результат работы программы — вывод 10 чисел из последовательности Фиббоначчи на консоль:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
В примерах выше функция напрямую вызывала саму себя. Но рекурсивный вызов функции также может быть косвенным. Например, функция fun1() вызывает другую функцию fun2(), которая, в свою очередь, вызывает fun1(). В этом случае функции fun1() и fun2() также называются взаимно рекурсивными функциями.
Стоит отметить, что нередко рекурсивные функции можно представить в виде циклов. Например, для вычисления факториала вместо рекурсии используем цикл:
#include unsigned long long factorial(unsigned); int main() < unsigned n ; std::cout unsigned long long factorial(unsigned n) < unsigned long long result; for(unsigned i; i return result; >
И нередко циклические конструкции более эффективны, чем рексурсия. Например, если функция вызывает себя тысячи раз, потребуется большой объем стековой памяти для хранения копий значений аргументов и адреса возврата для каждого вызова, что может привести к тому, что программа быстро исчерпает выделенную для нее память стека, поскольку объем памяти стека обычно фиксирован и ограничен. что может привести к аварийному завершению программы. Поэтому в таких случаях, как правило, лучше использовать альтернативные подходы, например цикл. Однако, несмотря на накладные расходы, использование рекурсии часто может значительно упростить написание программы.
Как выйти из рекурсии c
Собственно возврат стоит в самом начале а она один хер пробегает все дерево ваще недогоняю почему отладчиком статус все функции бывает истина
Процедура ЗаписатьЗначениеВ_ТЗБ(ТабПараметров,Стр,Ветка,ЭтоПлан=Ложь,Ключ=»»,СтатусВсейФункции=Ложь)
Если СтатусВсейФункции Тогда
Возврат;
КонецЕсли;
СтатусФункции =Ложь;
Для Каждого Узел Из Ветка.Строки Цикл
ИдентификаторУзла= Узел.N;
НаименованиеУзла = Узел.Наименование;
ЭтоНоваяСтрока=НаименованиеУзла = «Структура бюжета ООО ‘Интерполис'»;
Если ЭтоНоваяСтрока Тогда
Попытка
Если СтатусПроверкиТекущихДанных=0 Тогда
ЗаписатьТзВотстойник(ПредИдущаяТаблица);
КонецЕсли;
Исключение
КонецПопытки;
СтатусПроверкиТекущихДанных=0;
КонецЕсли;
ПредИдущаяТаблица=ТабПараметров;
Если ИдентификаторУзла<>Неопределено ТОгда
УровеньУзла= Узел.Уровень();
ЗначениеВетки= Узел.Значение;
НаименованиеВетки=СокрЛП(Узел.Наименование);
Если не ЭтоПлан или Ключ=ИдентификаторУзла Тогда
СтатусФункции = ПроверитьЗначениеВТЗБ(Узел,УровеньУзла,ЗначениеВетки,НаименованиеВетки,ТабПараметров,Стр,ИдентификаторУзла,ЭтоПлан);
Если СтатусФункции Тогда
СтатусПроверкиТекущихДанных=СтатусПроверкиТекущихДанных+1;
КонецЕсли;
КонецЕсли;
КонецЕсли;
ЗаписатьЗначениеВ_ТЗБ(ТабПараметров,Стр,Узел,ЭтоПлан,Ключ,СтатусФункции)
КонецЦикла;
КонецПроцедуры
а возврат происходит в первом вызове? раскрутка стэка