Стаття Нотатки про рекурсію
Програмісти вкладають у це поняття наступний зміст: рекурсія - це прийом програмування, у якому програма викликає себе чи безпосередньо, чи опосередковано.
Зазвичай програміст-початківець, який вперше почув про рекурсію, впадає в легке замішання. Здавалося б, немає нічого безглуздішого, ніж рекурсія. Подібний ланцюжок викликів ніколи не завершиться через зациклювання, або в кращому разі завершиться, але аварійно, коли завдання вичерпає всі готівкові ресурси комп'ютера.
Насправді рекурсія – це тонкий та витончений інструмент, який при вмілому використанні здатний послужити добру службу програмісту.
Справді, чому саме рекурсії випала честь одержати окрему статтю? Хіба це не рядовий прийом програмування, один із багатьох?
Особисто я виділяю рекурсію із загального ряду з багатьох причин. Ось деякі з них:
- Насамперед, рекурсія гарна. Початкове знайомство з нею може викликати нерозуміння і легкий шок, але, опанувавши цей механізм, ви навряд чи надалі зможете уникнути спокуси користуватися ним час від часу. Витонченість рекурсії у програмуванні я можу порівняти лише з витонченістю методу індукції з математики.
- Багато структур, як штучного, і природного походження, рекурсивні за своєю суттю. Розгляньте гілки та коріння дерев, структуру складної організації, ієрархію класів у складній програмі, фрактали – у будь-якій із цих структур ви знайдете численні повторення цілого в частині. Таким чином, багато сутностей природно можуть бути змодельовані рекурсивними структурами. А чим ще обробляти рекурсивну структуру, як не рекурсивною процедурою?
- Чимало завдань має також рекурсивну природу. Навіть, мабуть, більшістьнетривіальних завдань. Принаймні, у програмуванні далеко не новий метод декомпозиції завдання на дещо простіших, ті, у свою чергу, поділяються на ще простіші, і так доти, доки не дійдемо до елементарних частин, вирішити які досить просто. Звісно, програмісти є монополістами у цій галузі: подібними методами користуються архітектори, машинобудівники, математики
Будь-яке незнання зазвичай породжує масу забобонів. Наприклад, шаман племені людожерів, не маючи уявлення про атмосферну електрику, пояснює вдячним одноплемінникам, що гроза - це вияв немилості богів. І його слова приймаються за істину у першій інстанції, бо природа не терпить порожнечі, - там, де немає знання, поселяється забобон.
Рекурсія також обросла чутками та забобонами. Ви можете почути від комп'ютерних шаманів, що вона:
- безмірно марнотратно ставиться до пам'яті (кумедно, але я чув ці докази багато років тому, програмуючи на міні-ЕОМ PDP-11/40, яка "щедро" відводила на завдання користувача близько 50Кбайт; періодично мене намагаються залякати цим і зараз, коли обсяг ОЗУ в 1 Гбайт не є чимось надзвичайним);
- дуже накладна за ресурсами процесора; при цьому факт, що продуктивність мікропроцесорів Intel за минулі 10 років зросла як мінімум у 100 разів (якщо судити тільки за тактовою частотою, не враховуючи прогресу архітектури), якосьзовсім не береться до уваги;
- нарешті, складна у реалізації та налагодженні, що тягне за собою масу помилок у програмі; те, що помилки в заданні умов для циклів з перед- і постумовами, а також початкових і кінцевих значень у циклах з перебором значень зазвичай рясніють у типовій нерекурсивній програмі, конфузно замовчується.
Не відступатимемо від традиції і ми. При цьому, зрозуміло, приймемо вищесказане до відома і намагатимемося сприйняти наступний приклад просто як ілюстрацію до найпростішого застосування методу, а зовсім не як заклик весь залишок життя обчислювати факторіали саме таким чином.
Отже, пригадаємо, що таке факторіал. Позначається факторіал знаком оклику "!" і обчислюється так:
тобто є добуток натуральних чисел від 1 до N включно.
На цю функцію можна побачити і під іншим кутом зору. Уважніше вивчивши формулу(1), ми можемо дійти висновку, що
Таким чином ми визначили факторіал через сам факторіал! Здавалося б, таке визначення абсолютно марне, оскільки невідоме поняття визначається через знову ж таки невідоме поняття, і ми приходимо до нескінченного циклу. Однак це враження оманливе, тому що насправді факторіал N визначається через факторіал (N-1), тобто перебування невідомої функції зводиться до обчислення тієї ж невідомої функції від іншого аргументу, на одиницю меншого, ніж вихідний. Таким чином, є надія, що кожне наступне завдання вирішуватиметься трохи легше за попереднє.
Остаточно розірвати замкнене коло ми зможемо, якщо доповнимо рекурсивне визначення(2)ще одним, якеслужить чимось на зразок глухого кута, призначеного для зупинки процесу:
(Насправді слід було б обумовити поведінку факторіалу в нулі і при негативних значеннях аргументу, але оскільки в даний момент ми знайомимося з рекурсією, а не створюємо комерційну бібліотеку математичних функцій, опустимо несуттєві деталі).
Правила(2)та(3)спільно дозволяють обчислити значення факторіалу від будь-якого аргументу. Спробуємо для прикладу обчислити значення 5!, кілька разів застосувавши правило(2)і одноразово правило(3):
5! = 5*4! = 5*4*3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1
Ми отримали результат, що збігається з визначенням(1)з точністю до перестановки співмножників. (І самої перестановки в принципі можна було б уникнути, якщо перейти до(1)від правосторонньої рекурсії до лівосторонньої, але ці різновиди ми обговоримо пізніше).
Як виглядає рекурсія на практиці? Спробуємо реалізувати рекурсивне обчислення факторіалу як функції на C:
long int Fact(long int N) if (N #include
CBoard::CBoard(unsigned short n): m_Size(n) if (n = 0) && (j >= 0) && (і
CKnight::CKnight(CBoard *b): m_pBoard(b) >
void CKnight::Move(short x, short y, unsigned short n) m_pBoard->Move(x, y, n); >
void CKnight::MoveBack(short x, short y) m_pBoard->MoveBack(x, y); >
// спроба зробити хід n на клітину (x,y) bool CKnight::Try(short x, short y, unsigned short n) Move(x, y, n); // всі можливі ходи зроблені - успіх if (n == m_pBoard-CellsCount()) return true; // спробувати зробити наступний хід bool res = false; for(unsigned short i = 0; i CheckFree (x1, y1)) // спробувати його зробити res = Try (x1, y1, n + 1); // якщо хід успішний, припинити подальший перебір if (res) break; // невдалий хід - стерти його MoveBack(x1, y1); > > return res; > // Try
short CKnight::MoveX(unsigned short i) static short x[] = ; return x[i]; >
short CKnight::MoveY(unsigned short i) static short y[] = ; return y[i]; >
МетодиMoveтаMovebackтривіальні та просто делегують відповідні методи класуCBoard.