Airon007
09.10.2013, 15:39
Здравствуйте, уважаемые пользователи.
В этом уроке я хочу рассказать про процесс называемый "Рекурсия".
Постараюсь привести примеры и рассказать зачем и где используется.
Для начала, немножечко углубимся в теорию.
Рекурсия — процесс повторения элементов самоподобным образом.
Например, если два зеркала установить одно напротив другого, то возникающие в них вложенные отражения - это одна из форм бесконечной рекурсии.
Термин «Рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит саму себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.
С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Основное.
Рекурсия в PAWN.
Возможно, при компилировании мода вы могли заметить подобное сообщение:
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" или "Неизвестно" выводится тогда, когда компилятор не может посчитать максимальный объём памяти, используемой модом.
Это вызвано как раз использованием рекурсии, а детально нельзя посчитать сколько раз функция будет вызвана и какой объём памяти будет затрачен.
Теперь приведу пример, где компилятор смог рассчитать количество используемой памяти.
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
Как мы видим, слова "Unknown" уже нет. На его месте мы уже видим другую строчку:
estimated max. usage=3052 cells (12208 bytes)
которая сообщает нам, что мод будет затрачивать 3052(12208 байт) памяти из стека во время работы, что не превышает максимальный объём стека.
Примеры рекурсии в PAWN.
Вот тут, я постараюсь привести примеры и по возможности объяснить принцип их действия.
Пример 1:
main()
{
printf("%d", Test(2, 5)); // Напишет 64
}
stock Test(var,num)
{
if(num>=0)
{
return var*Test(var,num-1);
}
return 1;
}
Мы вызываем функцию Test с параметром 2 и 5. Напомню, что в нашей функции первый параметр - число которое возводим в степень, второй параметр - степень.
После вызова функции, она проверяет чему равна переменная num если она больше или равна (или равна, потому что отсчет в языках программирования идет с нуля), то функция умножает число на вызов самой себя, при этом num становится меньше на единицу. Зачем?
Надо помнить, что необходимо предусматривать выход из рекурсии. Иначе она станет бесконечной и ваш скрипт (а вместе с ним и сервер) зависнет.
В моем примере, выход из рекурсии - это
if(num>=0) и num-1.
Код выполняется только если num больше или равна нулю, а так как при каждом выполнении кода num уменьшается на один, бесконечной рекурсии не будет.
Попробуйте убрать выход из рекурсии и проверьте что будет.
______________________________________________________________________________________________________
Пример 2:
func(value)
{
printf("%d", ++value);
if(value < 50)
return func(value);
return true;
}
Мы вызываем функцию func с параметром value. В консоль сервера выводится значение параметра, а также прибавляется единица с помощью инкремента(++).
Дальше проверка, что если параметр value меньше 50 то вызвать функцию ещё раз, и так до того пока параметр value не будет равным 50.
______________________________________________________________________________________________________
Чем же опасна рекурсия для мода?
Рекурсия опасна тем, что при запуске функции из которой вызывается эта же самая функция, может переполнить память Стека и случится необратимый краш мода.
Другими словами - ввести в бесконечный цикл.
Но это случится, если рекурсия будет написана "криво".
Пример:
stock Test(var)
{
Test(var);
return 1;
}
Функция Test при вызове из другого скрипта войдёт в бесконечную рекурсию и в конечном итоге свалит мод в краш, так как функция вызывается из своего же "Тела" без очистки из Стека, что даст нам переполнение памяти.
Как можно найти рекурсию в моде?
Основываясь на своём опыте( так как сталкивался с такой проблемой) я сейчас детально постараюсь объяснить как можно найти рекурсивный код.
Для начала нужно проверить подключённые к моду инклуды на наличии рекурсий. Это можно сделать, подключив их к чистому new.pwn и скомпилировав.
Если сообщение о рекурсии после компилирования не выдастся то с инклудами всё нормально.
Коротенькое отступление: У меня вызывал рекурсию инклуды командного процессора YCMD (от Y_less).
y_master
y_command
Если же вы удостоверились, что рекурсии в инклудах нет, то принимайтесь за поиск рекурсивного кода в моде, в ручную.
Маленькая хитрость: при поиске рекурсии в моде я начал отключать по паблику / стоку (public / stock) и каждый раз компилировал. В конечном итоге я закомментировал нужный сток, и при компилировании рекурсия исчезла. Искать же сразу просто просматривая код, как мне кажется, не очень удачная мысль. Вы можете пропустить нужный код.
Я сначала приступил к очень внимательному просмотру код но потратил на это очень много времени и сил, и к тому же это не принесло пользы. В последствии догадался до способа описанного выше, и уже спустя час кропотливой работы компилятор не выдал сообщения о рекурсии.
Дополнительный материал.
Что же такое Стэк (Stack)?
Стек-(англ. stack — стопка) — структура данных, представляющая из себя список элементов организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Другими словами, Стек - это память в которой загружается информация о текущем паблике: его индекс, аргументы, кол-во аргументов.
Cтек очищается только после успешного выполнения паблика.
Размер Стека :16384(4096 байт).
Много важной информации хранится в stack'е, такой как техническая информация о текущей функции, из-за которой PAWN знает куда возвращаться. Используя слишком много памяти, вы можете перезаписать информацию в Стеке (это называется коллизией стека) и вернуться из функции в случайную точку в коде (или в секции данных), что означает неминуемый крэш. В конце концов ваша информация может быть испорчена, когда ее перезапишет другая информация
Я думаю, информации о Стеке должно хватить.
Автор: Mexanizm
В этом уроке я хочу рассказать про процесс называемый "Рекурсия".
Постараюсь привести примеры и рассказать зачем и где используется.
Для начала, немножечко углубимся в теорию.
Рекурсия — процесс повторения элементов самоподобным образом.
Например, если два зеркала установить одно напротив другого, то возникающие в них вложенные отражения - это одна из форм бесконечной рекурсии.
Термин «Рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит саму себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.
С рекурсией тесно связана математическая индукция: она является естественным способом доказательства свойств функций на натуральных числах, рекурсивно заданных через свои меньшие значения.
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Основное.
Рекурсия в PAWN.
Возможно, при компилировании мода вы могли заметить подобное сообщение:
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" или "Неизвестно" выводится тогда, когда компилятор не может посчитать максимальный объём памяти, используемой модом.
Это вызвано как раз использованием рекурсии, а детально нельзя посчитать сколько раз функция будет вызвана и какой объём памяти будет затрачен.
Теперь приведу пример, где компилятор смог рассчитать количество используемой памяти.
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
Как мы видим, слова "Unknown" уже нет. На его месте мы уже видим другую строчку:
estimated max. usage=3052 cells (12208 bytes)
которая сообщает нам, что мод будет затрачивать 3052(12208 байт) памяти из стека во время работы, что не превышает максимальный объём стека.
Примеры рекурсии в PAWN.
Вот тут, я постараюсь привести примеры и по возможности объяснить принцип их действия.
Пример 1:
main()
{
printf("%d", Test(2, 5)); // Напишет 64
}
stock Test(var,num)
{
if(num>=0)
{
return var*Test(var,num-1);
}
return 1;
}
Мы вызываем функцию Test с параметром 2 и 5. Напомню, что в нашей функции первый параметр - число которое возводим в степень, второй параметр - степень.
После вызова функции, она проверяет чему равна переменная num если она больше или равна (или равна, потому что отсчет в языках программирования идет с нуля), то функция умножает число на вызов самой себя, при этом num становится меньше на единицу. Зачем?
Надо помнить, что необходимо предусматривать выход из рекурсии. Иначе она станет бесконечной и ваш скрипт (а вместе с ним и сервер) зависнет.
В моем примере, выход из рекурсии - это
if(num>=0) и num-1.
Код выполняется только если num больше или равна нулю, а так как при каждом выполнении кода num уменьшается на один, бесконечной рекурсии не будет.
Попробуйте убрать выход из рекурсии и проверьте что будет.
______________________________________________________________________________________________________
Пример 2:
func(value)
{
printf("%d", ++value);
if(value < 50)
return func(value);
return true;
}
Мы вызываем функцию func с параметром value. В консоль сервера выводится значение параметра, а также прибавляется единица с помощью инкремента(++).
Дальше проверка, что если параметр value меньше 50 то вызвать функцию ещё раз, и так до того пока параметр value не будет равным 50.
______________________________________________________________________________________________________
Чем же опасна рекурсия для мода?
Рекурсия опасна тем, что при запуске функции из которой вызывается эта же самая функция, может переполнить память Стека и случится необратимый краш мода.
Другими словами - ввести в бесконечный цикл.
Но это случится, если рекурсия будет написана "криво".
Пример:
stock Test(var)
{
Test(var);
return 1;
}
Функция Test при вызове из другого скрипта войдёт в бесконечную рекурсию и в конечном итоге свалит мод в краш, так как функция вызывается из своего же "Тела" без очистки из Стека, что даст нам переполнение памяти.
Как можно найти рекурсию в моде?
Основываясь на своём опыте( так как сталкивался с такой проблемой) я сейчас детально постараюсь объяснить как можно найти рекурсивный код.
Для начала нужно проверить подключённые к моду инклуды на наличии рекурсий. Это можно сделать, подключив их к чистому new.pwn и скомпилировав.
Если сообщение о рекурсии после компилирования не выдастся то с инклудами всё нормально.
Коротенькое отступление: У меня вызывал рекурсию инклуды командного процессора YCMD (от Y_less).
y_master
y_command
Если же вы удостоверились, что рекурсии в инклудах нет, то принимайтесь за поиск рекурсивного кода в моде, в ручную.
Маленькая хитрость: при поиске рекурсии в моде я начал отключать по паблику / стоку (public / stock) и каждый раз компилировал. В конечном итоге я закомментировал нужный сток, и при компилировании рекурсия исчезла. Искать же сразу просто просматривая код, как мне кажется, не очень удачная мысль. Вы можете пропустить нужный код.
Я сначала приступил к очень внимательному просмотру код но потратил на это очень много времени и сил, и к тому же это не принесло пользы. В последствии догадался до способа описанного выше, и уже спустя час кропотливой работы компилятор не выдал сообщения о рекурсии.
Дополнительный материал.
Что же такое Стэк (Stack)?
Стек-(англ. stack — стопка) — структура данных, представляющая из себя список элементов организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Другими словами, Стек - это память в которой загружается информация о текущем паблике: его индекс, аргументы, кол-во аргументов.
Cтек очищается только после успешного выполнения паблика.
Размер Стека :16384(4096 байт).
Много важной информации хранится в stack'е, такой как техническая информация о текущей функции, из-за которой PAWN знает куда возвращаться. Используя слишком много памяти, вы можете перезаписать информацию в Стеке (это называется коллизией стека) и вернуться из функции в случайную точку в коде (или в секции данных), что означает неминуемый крэш. В конце концов ваша информация может быть испорчена, когда ее перезапишет другая информация
Я думаю, информации о Стеке должно хватить.
Автор: Mexanizm