Добро пожаловать на Pro Pawn - Портал о PAWN-скриптинге.
Страница 1 из 2 1 2 ПоследняяПоследняя
Показано с 1 по 10 из 12
  1. #1
    Аватар для Airon007
    Пользователь

    Статус
    Оффлайн
    Регистрация
    29.03.2013
    Адрес
    Республика Мордовия г.Саранск
    Сообщений
    484
    Репутация:
    46 ±

    Что такое рекурсия в pawn? [Пояснение]

    Здравствуйте, уважаемые пользователи.
    В этом уроке я хочу рассказать про процесс называемый "Рекурсия".
    Постараюсь привести примеры и рассказать зачем и где используется.

    Для начала, немножечко углубимся в теорию.


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

    Термин «Рекурсия» используется в различных специальных областях знаний — от лингвистики до логики, но наиболее широкое применение находит в математике и информатике. В математике и информатике рекурсия имеет отношение к методу определения функций: рекурсивно заданная функция в своём определении содержит саму себя, в частности, рекурсивной является функция, заданная рекуррентной формулой. Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

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

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

    Преимущество рекурсивного определения объекта заключается в том, что такое конечное определение теоретически способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.

    Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за счёт этого работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого, обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.



    Основное.

    Рекурсия в PAWN.





    Возможно, при компилировании мода вы могли заметить подобное сообщение:

    PHP код:
    Header size:           2644 bytes
    Code size
    :            47964 bytes
    Data size
    :            72096 bytes
    Stack
    /heap size:       16384 bytesestimated maxusageunknowndue to recursion
    Total requirements
    :  124504 bytes 
    *Цифры приведены примерные

    Обратим наше внимание на строчку
    PHP код:
    Stack/heap size:    16384 bytesestimated maxusageunknowndue to recursion 
    Попробуем собственно разобрать, что эта строчка значит.
    - Строка выводит сообщение о расчёте памяти используемой модом в процессе работы. Другими словами, компилятор рассчитывает используемую память из Стека(Stack) модом и выводит информацию.


    Теперь разберём детально.

    PHP код:
    Stack/heap size:    16384 bytes
    Это объём Стека в байтах.

    PHP код:
    estimated maxusageunknowndue to recursion 
    - В этой строчке приводится результат используемой максимальный памяти рассчитанный компилятором.
    На месте слова "unknown" должен собственно быть сам расчёт памяти(результат расчёта).
    "Unknown" или "Неизвестно" выводится тогда, когда компилятор не может посчитать максимальный объём памяти, используемой модом.
    Это вызвано как раз использованием рекурсии, а детально нельзя посчитать сколько раз функция будет вызвана и какой объём памяти будет затрачен.



    Теперь приведу пример, где компилятор смог рассчитать количество используемой памяти.
    PHP код:
    Header size:          14376 bytes
    Code size
    :          1923348 bytes
    Data size
    :          2137132 bytes
    Stack
    /heap size:      16384 bytesestimated maxusage=3052 cells (12208 bytes)
    Total requirements4091240 bytes 
    Как мы видим, слова "Unknown" уже нет. На его месте мы уже видим другую строчку:
    PHP код:
    estimated maxusage=3052 cells (12208 bytes
    которая сообщает нам, что мод будет затрачивать 3052(12208 байт) памяти из стека во время работы, что не превышает максимальный объём стека.


    Примеры рекурсии в PAWN.

    Вот тут, я постараюсь привести примеры и по возможности объяснить принцип их действия.

    Пример 1:

    PHP код:
    main()
    {
              
    printf("%d"Test(25)); // Напишет 64
    }

    stock Test(var,num)
    {
              if(
    num>=0)
              {
                  return var*
    Test(var,num-1);
              }
              return 
    1;

    [Font="Verdana]Мы вызываем функцию Test с параметром 2 и 5. Напомню, что в нашей функции первый параметр - число которое возводим в степень, второй параметр - степень.
    После вызова функции, она проверяет чему равна переменная num если она больше или равна (или равна, потому что отсчет в языках программирования идет с нуля), то функция умножает число на вызов самой себя, при этом num становится меньше на единицу. Зачем?
    Надо помнить, что необходимо предусматривать выход из рекурсии. Иначе она станет бесконечной и ваш скрипт (а вместе с ним и сервер) зависнет.
    В моем примере, выход из рекурсии - это
    if(num>=0) и num-1.
    Код выполняется только если num больше или равна нулю, а так как при каждом выполнении кода num уменьшается на один, бесконечной рекурсии не будет.
    Попробуйте убрать выход из рекурсии и проверьте что будет. [/FONT]

    ______________________________________________________________________________________________________

    Пример 2:

    PHP код:
    func(value)
    {
        
    printf("%d", ++value);
        if(
    value 50)
            return 
    func(value);
        return 
    true;

    Мы вызываем функцию func с параметром value. В консоль сервера выводится значение параметра, а также прибавляется единица с помощью инкремента(++).
    Дальше проверка, что если параметр value меньше 50 то вызвать функцию ещё раз, и так до того пока параметр value не будет равным 50.


    ______________________________________________________________________________________________________


    Чем же опасна рекурсия для мода?
    Рекурсия опасна тем, что при запуске функции из которой вызывается эта же самая функция, может переполнить память Стека и случится необратимый краш мода.
    Другими словами - ввести в бесконечный цикл.
    Но это случится, если рекурсия будет написана "криво".


    Пример:

    PHP код:
    stock Test(var)
    {
        
    Test(var);
        return 
    1;

    Функция Test при вызове из другого скрипта войдёт в бесконечную рекурсию и в конечном итоге свалит мод в краш, так как функция вызывается из своего же "Тела" без очистки из Стека, что даст нам переполнение памяти.


    Как можно найти рекурсию в моде?

    Основываясь на своём опыте( так как сталкивался с такой проблемой) я сейчас детально постараюсь объяснить как можно найти рекурсивный код.
    Для начала нужно проверить подключённые к моду инклуды на наличии рекурсий. Это можно сделать, подключив их к чистому new.pwn и скомпилировав.
    Если сообщение о рекурсии после компилирования не выдастся то с инклудами всё нормально.
    Коротенькое отступление: У меня вызывал рекурсию инклуды командного процессора YCMD (от Y_less).

    PHP код:
    y_master
    y_command 
    Если же вы удостоверились, что рекурсии в инклудах нет, то принимайтесь за поиск рекурсивного кода в моде, в ручную.
    Маленькая хитрость: при поиске рекурсии в моде я начал отключать по паблику / стоку (public / stock) и каждый раз компилировал. В конечном итоге я закомментировал нужный сток, и при компилировании рекурсия исчезла. Искать же сразу просто просматривая код, как мне кажется, не очень удачная мысль. Вы можете пропустить нужный код.

    Я сначала приступил к очень внимательному просмотру код но потратил на это очень много времени и сил, и к тому же это не принесло пользы. В последствии догадался до способа описанного выше, и уже спустя час кропотливой работы компилятор не выдал сообщения о рекурсии.



    Дополнительный материал.

    Что же такое Стэк (Stack)?
    Стек-(англ. stack — стопка) — структура данных, представляющая из себя список элементов организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).

    Другими словами, Стек - это память в которой загружается информация о текущем паблике: его индекс, аргументы, кол-во аргументов.
    Cтек очищается только после успешного выполнения паблика.
    Размер Стека :16384(4096 байт).
    Много важной информации хранится в stack'е, такой как техническая информация о текущей функции, из-за которой PAWN знает куда возвращаться. Используя слишком много памяти, вы можете перезаписать информацию в Стеке (это называется коллизией стека) и вернуться из функции в случайную точку в коде (или в секции данных), что означает неминуемый крэш. В конце концов ваша информация может быть испорчена, когда ее перезапишет другая информация
    Я думаю, информации о Стеке должно хватить.


    Автор: Mexanizm
    Последний раз редактировалось Daniel_Cortez; 10.10.2013 в 18:35. Причина: подправил некоторые факты
    Пробыл модератором на портале Pro-Pawn.Ru 3 месяца и 13 дней
    Ровно 105 дней провёл на посту СуперМодератора

  2. 3 пользователя(ей) сказали cпасибо:
    .Kos (01.02.2014) Danny_Marcelo (03.07.2016) Processing (01.05.2016)
  3. #2
    Аватар для Accord
    Пользователь

    Статус
    Оффлайн
    Регистрация
    16.11.2013
    Сообщений
    49
    Репутация:
    1 ±
    Полезная темка. Подниму!

  4. #3
    Аватар для Dimon_Gold
    Пользователь

    Статус
    Оффлайн
    Регистрация
    25.12.2013
    Сообщений
    17
    Репутация:
    0 ±
    ХАх оказывается у меня в моде была рекурсия!

  5. #4
    Аватар для Mexanizm
    Пользователь

    Статус
    Оффлайн
    Регистрация
    16.06.2014
    Сообщений
    15
    Репутация:
    2 ±
    Автор я. Кстате зачем на форуме два одинаковых урока ?

  6. #5
    Аватар для Osetin
    •Администратор•

    Статус
    Оффлайн
    Регистрация
    26.03.2013
    Адрес
    ♔Osetia, Vladikavkaz♔
    Сообщений
    3,432
    Репутация:
    1093 ±
    Цитата Сообщение от Mexanizm Посмотреть сообщение
    Автор я. Кстате зачем на форуме два одинаковых урока ?
    Указал автора, вторую тему удалил.

  7. 2 пользователя(ей) сказали cпасибо:
    Mexanizm (18.06.2014) Пельмень (18.06.2014)
  8. #6
    Аватар для Пельмень
    Пользователь

    Статус
    Оффлайн
    Регистрация
    05.12.2013
    Сообщений
    188
    Репутация:
    116 ±
    А теперь кратко что такое рекурсия по русски.

  9. 3 пользователя(ей) сказали cпасибо:
    Danny_Marcelo (03.07.2016) KShaddix (18.06.2014) L0ndl3m (18.06.2014)
  10. #7
    Аватар для underwoker
    Пользователь

    Статус
    Оффлайн
    Регистрация
    07.03.2014
    Сообщений
    331
    Репутация:
    47 ±


    - - - Добавлено - - -

    Вспомнил, поставьте два зеркала друг против друга. И будет опять та же рекурсия/
    "Власть, кровь, няш-мяш, кровь, власть, Крым наш!" - (c) Наталья Поклонская.

    Критик должен быть готов и способен в любой момент и по первому требованию занять место критикуемого им и выполнять его дело продуктивно и компетентно. В противном случае критика превращается в наглую, самодовлеющую силу и становится тормозом на пути прогресса. (с) AXE

  11. 3 пользователя(ей) сказали cпасибо:
    L0ndl3m (18.06.2014) Mexanizm (18.06.2014) Пельмень (18.06.2014)
  12. #8
    Аватар для DeimoS
    Модератор?

    Статус
    Оффлайн
    Регистрация
    27.01.2014
    Адрес
    Восточный Мордор
    Сообщений
    5,588
    Репутация:
    1984 ±
    - Что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - А что такое рекурсия?
    - Рекурсия - это рекурсия
    - ...
     Режисёрская версия концовки
    - А что такое рекурсия?
    - Бл*ть, ты идиот? Ты идиот...
    Последний раз редактировалось DeimoS; 18.06.2014 в 21:52.
    Связаться со мной в VK можно через личные сообщения этой группы
    Заказы не принимаю

    Широко известно, что идеи стоят 0.8333 цента каждая (исходя из рыночной цены 10 центов за дюжину).
    Великих идей полно, на них нет спроса.
    Воплощение идеи в законченную игру требует долгой работы,
    таланта, терпения и креативности, не говоря уж о затратах денег, времени и ресурсов.
    Предложить идею просто, воплотить – вот в чём проблема

    Steve Pavlina

  13. 3 пользователя(ей) сказали cпасибо:
    Danny_Marcelo (03.07.2016) L0ndl3m (18.06.2014) [ForD] (18.06.2014)
  14. #9
    Аватар для Mexanizm
    Пользователь

    Статус
    Оффлайн
    Регистрация
    16.06.2014
    Сообщений
    15
    Репутация:
    2 ±
    Это уже бесконечная рекурсия как и другие выше

  15. #10
    Аватар для L0ndl3m
    Пользователь

    Статус
    Оффлайн
    Регистрация
    19.10.2013
    Адрес
    Ярославль
    Сообщений
    1,366
    Репутация:
    774 ±
    Цитата Сообщение от DeimoS Посмотреть сообщение
    - Что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - А что такое рекурсия?
    - Это рекурсия
    - ...
    Это бесконечная рекурсия была? Попробуем сделать её с управлением.

    Начало.
    - Это рекурсия
    - А надо ещё рекурсии?
    - Да
    - А что такое рекурсия?
    - Это рекурсия
    - А надо ещё рекурсии?
    - Да
    - А что такое рекурсия?
    - Это рекурсия
    - А надо ещё рекурсии?
    - Да
    - А что такое рекурсия?
    - Это рекурсия
    - А надо ещё рекурсии?
    - Да
    - А что такое рекурсия?
    - Это рекурсия
    - А надо ещё рекурсии?
    - Нет
    - Ну хорошо
    Конец.

    Кто не понял в чём суть, посмотрите как устроена реализация, например факториала.

 

 
Страница 1 из 2 1 2 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •