Печера програміста Досвід відмови від рекурсії

Досвід відмови від рекурсії

В інтернеті практично не висвітлено тему відмови від рекурсії в алгоритмах. Багато статей та книг де розповідається, що таке рекурсія, як їй користуватися. Але ось як її позбудеться - майже нічого немає.

Отже, рекурсія – це виклик функцією самої себе. Усім відомий алгоритм обчислення факторіалу, класика книг. Все красиво та елегантно, хоч циклом здається і простіше. А вже всілякі алгоритми аналізу рядка та роботи з регулярними виразами. Здавалося б, використовуй та радуйся. Але не все так просто. Глибина рекурсії (як багато разів функція може викликати саму себе) обмежена. Обмежена розміром стека. Справа в тому, що перед викликом функцією самої себе потрібно зберегти значення всіх локальних змінних, щоб ними можна було скористатися після повернення. А зберігається це все у стек. І ось поки в стеку є місце, ми можемо заглиблюватись у рекурсію. Все глибше, глибше. Поки що не вискочить помилка - Stack overflow. І все, гасіть світло. Стандартна величина стека приблизно 2 мб (для windows програм). Так давайте збільшимо розмір стека налаштуваннями компілятора, ділов то. А на скільки збільшити, то щоб було і не багато і не мало? а якщо запити зростають з часом, постійно перекомпілювати? А якщо у вас бібліотека, яка використовує стек програми, що її викликала? І ось тут і розумієш, що це не наш метод. Треба якось позбавлятися рекурсії. Ось з цим я і зіткнувся в бібліотеці Colorer, що підтримується мною. Алгоритм розбору рядка за регулярним виразом був рекурсивний. Так само був гарний і пах. Але на довгих рядках любив падати. Дай рядок у 3000 символів і все приїхали. Треба було щось робити. Єдиним методом ліквідації рекурсії, який я знайшов, це порятунок від хвостовоїрекурсії. Суть його в наступному - якщо рекурсивний виклик йде останнім у функції, то можна замінити функцію на цикл. Факторіал є прикладом для цього. Але у мене рекурсивних викликів було дуже багато у функції. Частину можна було розгорнути в цикл, але це дуже мала частина. Та й, до речі, код був побудований так, що в залежності від результату виклику (функція повертала bool значення) функція могла завершитися або продовжити роботу далі. А сама функція була циклом усередині якого switch. Ось тут то приходить єдине рішення, що залишилося - а чому б нам не відтворити рекурсивний виклик за допомогою циклу і збереження параметрів? тобто. зробити все замість компілятора. Що нам для цього потрібно:

  1. список локальних змінних, які потрібно зберегти.
  2. динамічний список типу стека, в який ми зберігатимемо значення локальних змінних, і витягуватимемо від туди
  3. після-рекурсійні дії, або action (не знаю як назвати це краще)
  4. цикл
Спочатку зупинимося на action. Кожен рекурсійний виклик залежно від результату приводив до return true, або return false, або return результат_функції, або до продовження роботи функції багатьма рядками коду. Т.к. ми позбавляємося рекурсії на користь циклу, цей код потрібно виконати після завершення циклу для цього рекурсійного виклику. Тобто. коли цикл прийде до return. Тому всі такі ситуації виділяємо в один switch, присвоюючи їм свій код action.

Створюємо функцію, яка зберігає локальні змінні, а їхнє місце задає нові (якщо є параметри при виклику рекурсії). Як їх зберігати це окрема пісня. У мене їх було мало, і я передавав їх за посиланням. Крім змінних необхідно зберегти і дію (action) яке необхідно зробити залежно від результат функції.Ця функція замінює нам рекурсійний виклик – зберігаємо поточні значення, замінюємо їх на нові. Після збереження ми повинні повернутися на початок циклу, ніби ми тільки зайшли в функцію. Далі, створюємо функцію перевірки нашого стека на наявність там записів та вилучення їх із нього. Вона нам знадобиться для заміни рядків returnчого_то_там. Передаємо в неї цечого_то_там. І якщо стек порожній, повертаємо action =чего_то_там, інакше вилучаємо зі стека дані, оновлюємо локальні змінні і повертаємо action залежно відчего_то_там.За цим action виконуємо код.Ну а далі це все поєднуємо в один цикл і працюємо.

Загалом опис вийшов дуже сумбурний, малозрозумілий. Але пояснити важко. Простіше показати результат. Правилася функція CRegExp::lowParse. До змін файли були наступними: cregexp.cpp, cregexp.h. Після застосування цього методу cregexp.cpp, cregexp.h.

У ході випробувань підтвердилася стабільна робота на довгих рядках. Код працює коректно. Але трохи впала швидкість. На тестових файлах швидкість роботи впала на 1 секунду (на моєму комп'ютері). Після аналізу у профайлері, з'ясувалося, що вузьким місцем стала робота з пам'яттю у нашому стеку. Оптимізований варіант наведений вище як фінальний. У ньому падіння швидкості становить приблизно 0.4 секунди. Але це вже не усувається. Натомість ми не падаємо на рекурсії.

У новій версії FarColorer буде використано цей патч. І проблема, зафіксована у багатьох баг-репортах, нарешті таки піде.