Русское сообщество по скриптингу

Рекурсия, max. usage is unknown, due to recursion

Статьи или фрагменты кода для новичков и уже опытных скриптеров по AMXX.

Модератор: Chuvi

Правила форума
1. Запрещено материться и оскорблять других участников форума.
2. Запрещен флуд, оффтоп, дабл постинг во всех разделах форума, кроме раздела "Болтовня".
3. Запрещено взламывать сайт/форум или наносить любой вред проекту.
4. Запрещено рекламировать другие ресурсы.
5. Запрещено создавать темы без информативного названия. Название темы должно отображать ее смысл.

В данном разделе форума разрешено создавать темы, касающие только обучающему материалу по AMX Mod X.

Рекурсия, max. usage is unknown, due to recursion

Сообщение ko22009 » 02 фев 2017, 04:30

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

Что такое рекурсия?
Рекурсия вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A.

Например, косвенная рекурсия (Внимание, эта рекурсия бесконечна!):
Код: Выделить всё

public fn1
()
{
    fn2();
}
public fn2()
{
    fn1();
}

Например, прямая рекурсия (Внимание, эта рекурсия бесконечна!):
Код: Выделить всё

public fn1
()
{
    fn1();
}
 

Теперь перейдем непосредственно к компилятору.
При компиляции плагина вы могли замечать, следующую информацию
Например:
Код: Выделить всё
Header size:            144 bytes
Code size
:              116 bytes
Data size
:                0 bytes
Stack
/heap size:      16384 bytes; max. usage is unknown, due to recursion
Total requirements
:   16644 bytes

Из этого нам интересна строчка Stack/heap size:      16384 bytes; max. usage is unknown, due to recursion.
Она как раз нам дает понять, что компилятор не смог посчитать, сколько необходимо информации в стеке.

Стек - определенная область памяти, выполняющая определенные функции.
Стек может использоваться для разных целей:
  1. для организации прерываний, вызовов и возвратов;
  2. для временного хранения данных;
  3. для передачи и возвращения параметров при вызовах процедур.

По умолчанию amxx компилятор выделяет 16384 байтов (которые как раз указывает компилятор).
Если, вдруг у нас второй аргумент Stack/heap size становится больше этого объема, мы увеличиваем его размер через #pragma dynamic размер_стека_в_байтах.
Но, может случиться так, как в примере, мы увидим max. usage is unknown, due to recursion.

В этом случае необходимо устранять, если вы не уверены, что стек не перезаполнится и не вылетит сервер. Так как только стек перезаполняется вы получаете данные с другого участка памяти. То, как заполняется стек и освобождается, не для этой статьи.
Если вы уверены, что рекурсия не вызовет у вас переполнение стека и вам хватит этого кол-ва памяти, можете оставить так, как есть. Но не рекомендуется для средних и сложных проектов этого делать.
Рекурсия необходимо изменять на другие циклы.
Например, если у нас прямая рекурсия, то можно воспользоваться циклом с условием.
Пример с прямой рекурсией:
Код: Выделить всё

public recursion
(arg)
{
    if (arg < 1) return;
    recursion(arg--);
}

Пример с переписанной прямой рекурсией на цикл с условием:
Код: Выделить всё

public recursion_while
(arg)
{
    while(arg >= 1)
    {
        arg--;
    }
}

Почему именно у нас с прямой рекурсией возникает такая ошибка? Все потому, что мы не знаем точно сколько раз вызовется функция и сколько необходимо хранить в стеке информации. Во втором примере мы точно знаем, что она вызовется один раз, точнее она вызовет сама себе один раз. Компилятор не может посчитать это, так как он может считать только статистичекую информацию.

Бывает так, что мы не знаем где именно у нас рекурсия, в таком случае необходимо комментарировать код и проверять, когда у нас пропала ошибка. Другого варианта нет. После того как вы определите, где у вас возникает рекурсия, устраняйте.

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

Может быть также неявная рекурсия, т.е. рекурсии нет, но она происходит. Связано все из-за устаревшего amxmodx 1.8.2. Если вы используете сервер 1.8.2, то нужно компилировать под 1.8.2 и тогда не узнаете, сколько стека нужно. Но, есть выход, компилировать под 1.8.3 когда разрабатываете и когда нужно на боевой сервер, где стоит 1.8.2, тогда компилируете под 1.8.2. Под 1.8.3 вы увидите сколько вам требуется стека.
Код: Выделить всё

public first_function
()
{
    second_function();
}

public second_function()
{
}

public third_function()
{
    first_function();
    second_function();
}

Для ее устранения нужно часть кода second_function вставить в first_function. В результате second_function не вызывает first_function. А third_function не будет вызывать рекурсию. Либо не используйте second_function вместе с first_function

Если у вас есть другие типы рекурсий, буду рад о них узнать.
Надеюсь статья была полезна для вас.
Последний раз редактировалось ko22009 07 фев 2017, 16:56, всего редактировалось 3 раз(а).
Аватара пользователя
ko22009
 
Сообщения: 131
Зарегистрирован: 19 янв 2017, 16:20
Благодарил (а): 12 раз.
Поблагодарили: 27 раз.
Опыт программирования: Больше трех лет
Языки программирования: Pawn
C++
Php
Python
C#

Re: Рекурсия, max. usage is unknown, due to recursion

Сообщение RevCrew » 02 фев 2017, 14:15

Если вы уверены, что рекурсия не вызовет у вас переполнение стека и вам хватит этого кол-ва памяти, можете оставить так, как есть. Но не рекомендуется для средних и сложных проектов этого делать.

Причины какие? Это сугубо ваше мнение?
Аватара пользователя
RevCrew
Скриптер
 
Сообщения: 1648
Зарегистрирован: 15 июл 2013, 20:45
Благодарил (а): 273 раз.
Поблагодарили: 357 раз.
Языки программирования: Unkown

Re: Рекурсия, max. usage is unknown, due to recursion

Сообщение ko22009 » 02 фев 2017, 14:22

RevCrew писал(а):
Если вы уверены, что рекурсия не вызовет у вас переполнение стека и вам хватит этого кол-ва памяти, можете оставить так, как есть. Но не рекомендуется для средних и сложных проектов этого делать.

Причины какие? Это сугубо ваше мнение?

А вы как думаете?
Аватара пользователя
ko22009
 
Сообщения: 131
Зарегистрирован: 19 янв 2017, 16:20
Благодарил (а): 12 раз.
Поблагодарили: 27 раз.
Опыт программирования: Больше трех лет
Языки программирования: Pawn
C++
Php
Python
C#

Re: Рекурсия, max. usage is unknown, due to recursion

Сообщение Subb98 » 02 фев 2017, 14:26

Хотелось бы только добавить, что сама по себе рекурсия не критична, если нельзя сделать иначе и если число её вызовов не запредельное / не бесконечное.
«Очень хорошо. Лучше вы, чем я» © Donald J. Trump
Аватара пользователя
Subb98
Модератор
 
Сообщения: 5485
Зарегистрирован: 24 мар 2011, 19:42
Откуда: г. Пермь
Благодарил (а): 1329 раз.
Поблагодарили: 2343 раз.
Опыт программирования: Больше трех лет
Языки программирования: PHP

Re: Рекурсия, max. usage is unknown, due to recursion

Сообщение RevCrew » 02 фев 2017, 14:54

ko22009, это я вам вопрос задал
Аватара пользователя
RevCrew
Скриптер
 
Сообщения: 1648
Зарегистрирован: 15 июл 2013, 20:45
Благодарил (а): 273 раз.
Поблагодарили: 357 раз.
Языки программирования: Unkown

Re: Рекурсия, max. usage is unknown, due to recursion

Сообщение ko22009 » 02 фев 2017, 15:24

RevCrew писал(а):ko22009, это я вам вопрос задал

Это мое личное мнение. Да и думаю, переполнение стека может не очень хорошо повлиять на сервер. Если программировать, то качественно. Рекурсия не позволяет увидеть сколько памяти необходимо для работы скрипта.
Аватара пользователя
ko22009
 
Сообщения: 131
Зарегистрирован: 19 янв 2017, 16:20
Благодарил (а): 12 раз.
Поблагодарили: 27 раз.
Опыт программирования: Больше трех лет
Языки программирования: Pawn
C++
Php
Python
C#

Re: Рекурсия, max. usage is unknown, due to recursion

Сообщение Pafos » 03 фев 2017, 00:44

ko22009, почему в первых двух примерах код не оттабулирован?
Аватара пользователя
Pafos
 
Сообщения: 574
Зарегистрирован: 07 апр 2014, 18:03
Откуда: pfnClientConnect
Забанен
Благодарил (а): 129 раз.
Поблагодарили: 97 раз.
Опыт программирования: Больше трех лет
Языки программирования: Pawn

Re: Рекурсия, max. usage is unknown, due to recursion

Сообщение ko22009 » 03 фев 2017, 06:34

Pafos писал(а):ko22009, почему в первых двух примерах код не оттабулирован?

Исправил :thumbs_up
Аватара пользователя
ko22009
 
Сообщения: 131
Зарегистрирован: 19 янв 2017, 16:20
Благодарил (а): 12 раз.
Поблагодарили: 27 раз.
Опыт программирования: Больше трех лет
Языки программирования: Pawn
C++
Php
Python
C#


Вернуться в Статьи / фрагменты кода

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4