Рекурсия и с чем её едят
Здравствуйте уважаемые пользователи.
В этом уроке я хочу рассказать пр процесс называемый "Рекурсия".
Постараюсь привести примеры и рассказать зачем и где используется.
Сначала немножечко углубимся в теорию.
Реку́рсия — процесс повторения элементов самоподобным образом. Например, если два зеркала установить одно напротив другого, то возникающие в них вложенные отражения - это одна из форм бесконечной рекурсии.
Термин «рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит саму себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.
С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Основное
Возможно при компилировании мода вы могли заметить вот такое сообщение:Пример:
*Цифры приведены примерныеКод:Header size: 2644 bytes Code size: 47964 bytes Data size: 72096 bytes Stack/heap size: 16384 bytes; estimated max. usage: unknown, due to recursion Total requirements: 124504 bytes
Обратим наше внимание на строчкуПопробуем собственно разобрать что эта строчка значит.Код:Stack/heap size: 16384 bytes; estimated max. usage: unknown, due to recursion
- Строка выводит сообщение о расчёте памяти используемой модом в процессе работы. Другими словами компилятор рассчитывает используемую память из Стека(Stack) модом и выводит
информацию.
Теперь разберём детально.
Это объём Стека в байтах.Код:Stack/heap size: 16384 bytes;
- В этой строчке приводится результат используемой максимальный памяти рассчитанный компилятором.Код:estimated max. usage: unknown, due to recursion
На месте слова "unknown" должен собственно быть сам расчёт памяти(результат расчёта).
"Unknown" или "Неизвестно" выводится тогда когда компилятор не может посчитать максимальный объём памяти используемый модом.
Это вызвано как раз использованием рекурсии, а детально не может посчитать сколько раз функция будет вызвана и какой объём памяти она затратит(вроде так).
Теперь приведу пример, где компилятор смог рассчитать количество используемой памяти
Как мы видим, слова"Unknown" уже нет. На его месте мы уже видим другую строчкуКод:Header size: 14376 bytes Code size: 1923348 bytes Data size: 2137132 bytes Stack/heap size: 16384 bytes; estimated max. usage=3052 cells (12208 bytes) Total requirements: 4091240 bytesкоторая сообщает нам, что мод будет затрачивать 3052(12208 байт) памяти из Стека во время работы, что не превышает максимальный объём Стека.Код:estimated max. usage=3052 cells (12208 bytes)
В этой ветке я постараюсь привести примеры и по возможности объяснить принцип их действия.
Пример 1:
Мы вызываем функцию Test с параметром 2 и 5. Напомню, что в нашей функции первый параметр - число которое возводим в степень, второй параметр - степень.PHP код:main()
{
printf("%d", Test(2, 5)); // Напишет 64
}
stock Test(var,num)
{
if(num>=0)
{
return var*Test(var,num-1);
}
return 1;
}
После вызова функции, она проверяет чему равна переменная num если она больше или равна (или равна, потому что отсчет в языках программирования идет с нуля), то функция умножает число на вызов самой себя, при этом num становится меньше на единицу. Зачем?
Надо помнить, что необходимо предусматривать выход из рекурсии. Иначе она станет бесконечной и ваш скрипт (а вместе с ним и сервер) зависнет.
В моем примере, выход из рекурсии - это
if(num>=0) и num-1.
Код выполняется только если num больше или равна нулю, а так как при каждом выполнении кода num уменьшается на один, бесконечной рекурсии не будет.
Попробуйте убрать выход из рекурсии и проверьте что будет.
__________________________________________________ __________________________________________________ __
Пример 2:
Мы вызываем функцию func с параметром value. В консоль сервера выводится значение параметра, а также прибавляется единица с помощью инкремента(++)PHP код:func(value)
{
printf("%d", ++value);
if(value < 50)
return func(value);
return true;
}
Дальше проверка, что если параметр value меньше 50 то вызвать функцию ещё раз, и так до того пока параметр value не будет равным 50.
__________________________________________________ __________________________________________________ __
Рекурсия опасна тем, что при запуске функции из которой вызывается эта же самая функция, может переполнить память Стека и случится необратимый краш мода.
Другими словами ввести в бесконечный цикл.(вроде так)
Но это случится если рекурсия будет написана "Криво".
Пример:
Функция Test при вызове из другого скрипта войдёт в бесконечную рекурсию и в конечном итоге свалит мод в краш, так как функция вызывается из своего же "Тела" без очистки из Стека, что даст нам переполнение памяти.PHP код:stock Test(var)
{
Test(var);
return 1;
}
Основываясь на своём опыте( так как сталкивался с такой проблемой) я щас детально постараюсь объяснить как можно найти рекурсивный код.
Для начала нужно проверить подключённые к моду инклуды на наличии рекурсий. Это можно сдлелать, подключив их к чистому new.pwn и скомпилировав.
Если сообщение о рекурсии после компилирования не выдастся то с инклудами всё нормально.
Коротенькое отступление: У меня вызывал рекурсию инклуды командного процессора YCMD (от Y_less).
Если же вы удостоверились, что рекурсии в инклудах нет, то принимайтесь за поиск рекурсивного кода в моде, в ручную.PHP код:y_master
y_command
Маленькая хитрость: при поиске рекурсии в моде я начал отключать по паблику / стоку (public / stock) и каждый раз компилировал. В конечном итоге я закомментировал нужный сток, и при компилировании рекурсия исчезла. Искать же сразу просто просматривая код, как мне кажется, не очень удачная мысль. Вы можете пропустить нужный код.
Я сначала приступил к очень внимательному просмотру код но потратил на это очень много времени и сил, и к тому же это не принесло пользы. В последствии догадался до способа описанного выше, и уже спустя час кропотливой работы компилятор не выдал сообщения о рекурсии.
Также нашёл рекурсивный код в моде RLS.
Может пригодится...
PHP код:stock StartSpectate(playerid, specid)
{
for(new x=0; x<GetMaxPlayers(); x++)
{
if(GetPlayerState(x) == PLAYER_STATE_SPECTATING && gSpectateID[x] == playerid)
{
AdvanceSpectate(x);
}
}
if(IsPlayerInAnyVehicle(specid))
{
SetPlayerInterior(playerid,GetPlayerInterior(specid));
SetPlayerVirtualWorld(playerid, GetPlayerVirtualWorld(specid));
TogglePlayerSpectating(playerid, 1);
PlayerSpectateVehicle(playerid, GetPlayerVehicleID(specid));
gSpectateID[playerid] = specid;
gSpectateType[playerid] = ADMIN_SPEC_TYPE_VEHICLE;
}
else
{
SetPlayerInterior(playerid,GetPlayerInterior(specid));
SetPlayerVirtualWorld(playerid, GetPlayerVirtualWorld(specid));
TogglePlayerSpectating(playerid, 1);
PlayerSpectatePlayer(playerid, specid);
gSpectateID[playerid] = specid;
gSpectateType[playerid] = ADMIN_SPEC_TYPE_PLAYER;
}
new ping = GetPlayerPing(specid);
new Float:health;
GetPlayerHealth(specid, health);
new string[100], name[24];
GetPlayerName(specid,name,sizeof(name));
new lvl = PlayerInfo[specid][pLevel];
new warns = PlayerInfo[specid][pWarns];
format(string,sizeof(string),"~n~~n~~n~~n~~n~~n~~n~~w~%s ID:%d~n~ LVL: %d Warns: %d ~n~ HP: %.0f ~r~PING: %d ", name,specid,lvl,warns,health,ping);
GameTextForPlayer(playerid,string,9999,3);
return 1;
}
stock AdvanceSpectate(playerid)
{
if(ConnectedPlayers() == 2) { StopSpectate(playerid); return 1; }
if(GetPlayerState(playerid) == PLAYER_STATE_SPECTATING && gSpectateID[playerid] != INVALID_PLAYER_ID) {
for(new x=gSpectateID[playerid]+1; x<=GetMaxPlayers(); x++) {
if(x == MAX_PLAYERS) { x = 0; }
if(IsPlayerConnected(x) && x != playerid) {
if(GetPlayerState(x) == PLAYER_STATE_SPECTATING && gSpectateID[x] != INVALID_PLAYER_ID ||
(GetPlayerState(x) != 1 && GetPlayerState(x) != 2 && GetPlayerState(x) != 3))
{
continue;
}
else
{
StartSpectate(playerid, x);
break;
}
}
}
}
return 1;
}
Дополнительный материал
Стек (англ. stack — стопка) — структура данных, представляющая из себя список элементов организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Другими словами Stack или Heap(куча) это память в которой загружается информация о текущем паблике: его индекс, аргументы, кол-во аргументов
стек очищается только после успешного выполнения паблика.
Размер Стека :16384(4096 байт).
Много важной информации хранится в stack'е, такой как техническая информация о текущей функции, из-за которой PAWN знает куда возвращаться. Используя слишком много памяти, вы можете переписать информацию в stack, возвращая(returning) в случайную точку в коде, что означает абсолютный крэш. В конце концов ваша информация может быть испорчена, когда ее перезапишет другая информация
Я думаю информации о Стеке должно хватить
Благодарю вас за ознакомление с моим уроком. В нём я постарался изложить всю доступную мне информацию, которую пришлось пережить на горьком опыте.
Также использовал достаточно информации с других источников таких как Википедия, Лукоморье, samp com.
Некоторую информацию про Стек я позаимствовал из урока Владокса "Переполнение стека, или "почему нельзя возвращать массивы"".
Благодарю Frog163 за предоставление второго примера рекурсии. Также, первые два примера я позаимствовал у человека с ником _Dark_
Автор данного урока я, то есть Mexanizm93
Уважаемые форумчане.
Буду рад выслушать возможную критику по данному уроку.
С ваших замечаний и рекомендаций буду дополнять урок и исправлять места где ошибся.
Спасибо за просмотр урока
Урок написан специально для lightcode.ru. При копировании материала на другие источники прошу указывать ссылку на оригинал и автора урока.
Спасибо
Автор данного урока я, то есть Mexanizm93
Привет! Если вы читаете это - вы еще не зарегистрированы. Это займет не больше минуты. Нажмите здесь, чтобы пройти регистрацию в несколько простых шагов, чтобы получить доступ ко всем разделам нашего форума. Удачи!
Теория
Теория
Ответить с цитированием
Сообщение от RastaOrecha
