бідною рекурсії замовте слово, або все, що ви не знали і не хочете про неї знати

Рекурсія: див. рекурсія.
Всі програмісти поділяються на 112 категорій: хто не розуміє рекурсію, хто вже зрозумів, і хто навчився нею користуватися. Загалом, гурилка з мене виключно картонний, так що осягати Дао Рекурсії тобі, читачу, все одно доведеться самостійно, я лише спробую видати кілька чарівних пенделей в потрібному напрямку.

Прикладне програмування завжди займається вирішенням прикладних задач шляхом прикладання зусиль програміста для досягнення результату в неідеальних умовах. Саме виходячи з неідеальності цього світу і обмеженість ресурсів і складається потреба в програмістах: адже комусь треба допомагати теоретикам упихать їх струнку і красиву теорію в практику.

— Як вона складена?
— Чудово! Тільки рука трохи стирчить з валізи.
Саме намагаючись розмістити струнку теорію алгоритму в жорсткий рюкзак реальних ресурсів і доводиться постійно кроїти по живому, перепаковувати, і замість красивих і струнких визначень Фібоначчі:

def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
if n>1: return fib(n-1) + fib(n-2)
return n

доводиться городити всілякі брудні хакі, починаючи від:

@memoized
def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
if n>1: return fib(n-1) + fib(n-2)
return n

І закінчуючи взагалі:

def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
n0 = 0
n1 = 1
for k in range(n):
n0, n1 = n1, n0+n1
return n0


Так що ж таке рекурсія?
Рекурсія, по суті, це доказ по індукції. Ми розповідаємо, як отримати результат для якогось стану, припускаючи що у нас є результат для іншого набору станів, так само розповідаємо, як отримати результат у тих станах, до яких все скочується так чи інакше.

Якщо ви чекаєте гостей і раптом помітили на своєму костюмі пляма, не засмучуйтеся. Це можна виправити.
Наприклад, плями від рослинного масла легко виводяться бензином. Плями від бензину легко знімаються розчином лугу.
Плями від лугу зникають від оцтової есенції. Сліди від оцтової есенції треба потерти соняшниковою олією.
Ну, а як виводити плями від олії, ви вже знаєте...
Тепер давайте розглянемо класичний приклад: обхід дерева в глибину. Втім ні, давайте розглянемо інший приклад: нам треба роздрукувати дерево виразів у формі зворотного польського запису. Тобто для дерева 1 ми хочемо надрукувати «2 2 +» а для дерева 2 «2 2 + 2 2 + *».

tex
\begin{tikzpicture}
\node (is-root) {+}
child { node {2} }
child { node {2} };
\path (is-root) +(0,+0.5\tikzleveldistance)
node {\textit{Tree 1}};
\end{tikzpicture}
\begin{tikzpicture}
\node (is-root) {*}
child { node {+} [sibling distance=1cm] child {node{2}} child {node{2}} }
child { node {+} [sibling distance=1cm] child {node{2}} child {node{2}} };
\path (is-root) +(0,+0.5\tikzleveldistance)
node {\textit{Tree 2}};
\end{tikzpicture}


Як легко бачити, завдання перетворюється в простий «обхід дерева в глибину»: для кожного вузла виводимо вміст всіх його дочірніх елементів, після чого виводимо сам вузол. Тобто код:

class TreeNode(object):
def __init__(self, value=None, children=[]):
self.value = value
self.children = children
def printTree(node):
for child in node.children:
printTree(child)
print node.value,
def main():
tree1 = TreeNode("+", [ TreeNode(2), TreeNode(2) ])
tree2 = TreeNode(".*", [ TreeNode("+", [ TreeNode(2), TreeNode(2) ]), TreeNode("+", [ TreeNode(2), TreeNode(2) ]) ])
print "Tree1:",
printTree(tree1)
print

print "Tree2:",
printTree(tree2)
print
if __name__ == "__main__":
main()


Здавалося б, все відмінно! Код прекрасно працює до тих пір, поки дерево відповідає вимогам: будь-який вузол має масив дітей (можливо порожній) і яке-небудь значення. Хто скаже яке ще вимога до цього дерева?



Не буду мучити. Вимога: не сильно велика глибина дерева. Як так? А ось як:

def buildTree(depth):
root = TreeNode("1")
node = root
for k in range(depth):
node = TreeNode("--", [ node ])
return node

def depthTest(depth):
tree = buildTree(depth)
print "Tree of depth", depth, ":",
printTree(tree)

def main():
for d in range(10000):
depthTest(d)

Запускаємо, і ууупс! «Tree of depth 997: RuntimeError: maximum recursion depth exceeded». Ліземо в документацію, і виявляємо функцію sys.getrecursionlimit. А тепер давайте відійдемо від світу інтерпретованих мов, і перейдемо в світ мов, які запускаються прямо на процесорі. Наприклад, на C++.

Подумки перепишемо 1-в-1 цей код на С++ (залишу цю задачу читачеві в якості розминки), і спробуємо знайти межа, коли додаток упреться в обмеження…

для ледачих
#include < string>
#include < vector>
#include < iostream>

using namespace std;

class TreeNode {
public:
string value_;
vector<TreeNode*> children_;

TreeNode(const string& value, const vector<TreeNode*>& children):
value_(value), children_(children) {}

virtual ~TreeNode() {}
};

void printTree(const TreeNode* node) {
for(auto i : node->children_)
printTree(i);
cout << node->value_ << " ";
}

TreeNode* buildTree(const int depth) {
auto root = new TreeNode("1", {});
auto node = root;
for(int i = 0; i<depth; i++) {
vector<TreeNode*> children;
children.push_back(node);
node = new TreeNode("--", children);
}
return node;
}

void depthTest(const int depth) {
auto tree = buildTree(depth);
cout << "Tree of depth " << depth << ": ";
printTree(tree);
cout << endl;
}

int main() {
for(int d=60000;; d+=16384) {
depthTest(d);
}
}

Запускаємо… «Bus error (dumped core)». Судячи з gdb, у момент падіння стек глибиною 104790 фреймів. А що станеться, якщо ми захочемо друкувати не просто поспіль через прогалини, а виводити ще "{" і "}" навколо виразів? Ну тобто для дерева 1 щоб результатом було {2 2 +} а для дерева 2 — {{2 2 +}{2 2 +}*}? Перепишемо…

def printTree(node):
opened = False
for child in node.children:
if not opened:
print "{",
opened = True
printTree(child)
print node.value,
if opened:
print "}",


Нічого не змінилося, як і раніше падає при спробі надрукувати дерево глибиною 997. А тепер те ж саме, але на плюсах… Опа. Глибина стека при падінні — 87327. Стоп. Ми всього-то додали одну локальну змінну, ніяк не впливає на алгоритм і суть того, що відбувається, а граничний розмір дерева скоротився на 17%! А тепер саме веселе — все це сильно залежить від опцій компілятора, від того, на якій платформі виконується, в якій ОС і з якими налаштуваннями.

Але це не найсмішніше. Давайте уявимо, що цю функцію використовує інша функція. Все добре, якщо вона одна така — ми можемо підрахувати, на скільки ж фактичних кроків менше максимальна глибина. А якщо ця функція використовується з іншого рекурсивну? Тоді можливості цієї функції будуть залежати від глибини іншої функції.

Ось таким чином наш прекрасний простий алгоритм перестає раптово влазити в наш недосконалий валізу. Надам читачеві самому представити як добре мати подібні обмеження в сервісі, який запущено в продакшені і надає якийсь сервіс нічого не підозрюють хакерам, які тільки і роблять, що тикають в цей сервіс своїми брудними fuzzy тестерами.

Так в чому ж проблема?
Використання рекурсивного алгоритму передбачає використання практично не контрольованого ресурсу: стека викликів.

По-1х, ми не можемо точно знати скільки вже використано. По-2х, ми не можемо точно знати, скільки ще залишилося. В-3их ми не можемо гарантувати доступність певного розміру цього ресурсу до кожного викликом. У 4-х, ми не можемо фіксувати витрати даного ресурсу. Таким чином, ми потрапляємо в залежність від ресурсу, контролювати і розподіляти який біса складно. В результаті, ми не можемо гарантувати жодних характеристик даної функції/сервісу. Добре, якщо наш сервіс працює в managed контексті: java, python, .net ітп. Погано, якщо сервіс працює в неконтрольованої середовищі: javascript (з яким взагалі все погано). Ще гірше, якщо сервіс працює на C++, і глибина рекурсії залежить від даних, переданих користувачем.

Що ж робити?
Якщо ми працюємо не на мікроконтролері, про обсязі стека можна не замислюватися: для звичайної ланцюжка викликів його повинно вистачати. За умови, звісно, що ми дбаємо гігієни локальних змінних: великі об'єкти та масиви виділяються використовуючи пам'ять (new/malloc). Однак використання рекурсії має на увазі, що замість обмеженої кількості викликів, у нас їх буде просто рахункове.

Отже, щоб позбутися від проблем, створених рекурсією, можна зробити наступне (від простого до складного):
— Жорстко обмежити максимальний розмір/формат/числа у вхідних даних. Привіт, zip бомбам і іже з ними — іноді навіть маленький вхідний пакет може влаштувати великий переполох.
— Жорстко обмежити максимальну глибину викликів деяким числом. Важливо пам'ятати, що це число повинне бути ДУЖЕ невеликим. Тобто порядку сотень. І обов'язково додати тести, які перевіряють, що програма з цим максимальним числом не ламається. Причому з максимальним числом на всіх можливих гілках виконання (привіт виділення локальних змінних на вимогу). І не забувати перевіряти цей тест на різних опціях компилияции і після кожного білду.
— Жорстко обмежити обсяг використовуваний стека. Використовуючи складні обхідні маневри і знання про практичної реалізації виконання в залозі можна отримати розмір стека, який використаний зараз (типу взяття адреси локальної volatile змінної). У деяких випадках (наприклад, через libunwind в linux'е) можна отримати так само доступний об'єм стека поточного потоку, і взяти між ними різницю. При використанні такого методу важливо мати тести, що перевіряють, що відсікання працює гарантовано і при всіх варіантах вхідних даних — наприклад, може вийти весело, якщо перевірка йде в одному методі, який рекурсивен через 3-4 інших. І воно може впасти в проміжному… Але тільки в режимі релізу, після inline'а деяких функцій, наприклад. Втім, тут ще важливі тести на максимальну допустиму складність, щоб ненароком не відсікти частину коректних вхідних запитів, якими клієнти реально користуються.
— Кращий спосіб: позбавитися від рекурсії.

І не бреши, що ти вільний і свят — Ти полонений і неволен.
Я розкрив перед тобою небосхил!
Часи змінюють свій хід — Подивися на долоні…

Безмежна насолода свободи
Відкинути свободу
© Сергій Калугін
Так-так. Після осягнення Дао рекурсії осягаєш так само Дао відмови від рекурсії. Практично всі рекурсивні алгоритми мають нерекурсивные аналоги. Починаючи від більш ефективних (див. вище Фібоначчі), і закінчуючи еквівалентними, використовують чергу в пам'яті замість стека викликів.

Канонічна нерекурсивная реалізацію обходу дерева в глибину:
def printTree(node):
stack = [ (node, False, False) ]
while len(stack)>0:
i = len(stack)-1
node, відвідали, opened = stack[i]
if not відвідали:
for child in reversed(node.children):
if not opened:
print "{",
opened = True
stack.append( (child, False, False) )
відвідали = True
stack[i] = (node, відвідали, opened)
else:
print node.value,
if opened:
print "}",
del stack[i]

Як легко бачити, алгоритм не змінився, але замість використання стека викликів використовується масив stack, розміщений у пам'яті, і зберігає як контекст обробки (в нашому випадку — прапор opened) так і контекст обробки (в нашому випадку — до чи після обробки дітей). У випадках, коли потрібно щось робити між кожним з рекурсивних викликів, які додаються фази обробки. Зверніть увагу: це вже оптимізований алгоритм, який складав всіх дітей в стек відразу, і саме тому який складав у зворотному порядку. Це гарантує збереження того ж порядку, що і у вихідного нерекурсивного алгоритму.

Ось цей самий код, тільки написаний «в лоб», зберігаючи контекст (заодно, виводить коми між елементами):

def printTree(node):
stack = [ (node, 0) ]
while len(stack)>0:
i = len(stack)-1
node, phase = stack[i]
if phase < len(node.children):
child = node.children[phase]
if phase == 0:
print "{",
if phase > 0:
print ",",
stack.append( (child, 0) )
stack[i] = (node, phase+1)
else:
print node.value,
if phase>0:
print "}",
del stack[i]

Так, перехід на безрекурсивные технології не зовсім безкоштовний: ми платимо періодично більш дорогим — динамічним виділенням пам'яті для організації стека. Втім, це окупається: у «ручний стек» зберігаються не взагалі всі локальні змінні, а лише мінімально необхідний контекст, розмір якого вже можна контролювати. Друга стаття витрат: читабельність коду. Код, записаний у нерекурсивном вигляді дещо складніше для сприйняття за рахунок розгалужень від поточного стану. Рішення цієї проблеми лежить в області організації коду: винесення кроків в окремі функції і грамотне їх найменування.

Пригода
Незважаючи на наявність якогось «податку на обезрекурсивание», я особисто вважаю його обов'язковим до сплати в будь-якому місці, де йде обробка даних, так або інакше що надійшли від користувача.

А як не використовуєте рекурсію ви?

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.