Рекурсії - це що? Рекурсія в програмуванні (приклади)

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

Що таке "рекурсія" взагалі?

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

Що мають на увазі під рекурсією в програмуванні?

Рекурсивними ситуаціями, або рекурсією в програмуванні, називають моменти, коли процедура або функція програми викликає саму себе. Як би дивно для тих, хто почав вивчати програмування, це не звучало, тут немає нічого дивного. Слід запам'ятати, що рекурсії - це не складно, і в окремих випадках вони замінюють цикли. Якщо комп'ютеру правильно задати виклик процедури або функції, він просто почне її виконувати.

Рекурсія може бути кінцевою або нескінченною. Для того щоб перша припинила сама себе викликати, в ній же повинні бути умови припинення. Це може бути зменшення значення змінної і при досягненні певного значення зупинка виклику і завершення програми / перехід до подальшого коду, в залежності від потреб досягти певних цілей. Під нескінченної рекурсією подразумевают, що вона буде викликатися, поки працюватиме комп'ютер або програма, в якій вона працює.

Можлива також організація складної рекурсії за допомогою двох функцій. Припустимо, є А і Б. Функція А має в своєму коді виклик Б, а Б, у свою чергу, вказує комп'ютеру на необхідність виконати А. Складні рекурсії - це вихід з цілого ряду складних логічних ситуацій для комп'ютерної логіки.

Якщо хто читає ці рядки вивчав програмні цикли, то він, напевно, вже помітив схожість між ними і рекурсією. В цілому вони дійсно можуть виконувати схожі або ідентичні завдання. За допомогою рекурсії зручно робити імітацію роботи циклу. Особливо це корисно там, де самі цикли використовувати не дуже зручно. Схема програмної реалізації не сильно різниться у різних високорівневих мов програмування. Але все ж рекурсія в "Паскалі" і рекурсія в С або іншою мовою має свої особливості. Може вона бути успішно реалізована і в низькорівневих мовах кшталт "Асемблера", але це є більш проблематичним і витратним за часом.

Дерева рекурсії

Що таке "дерево" у програмуванні? Це кінцеве безліч, що складається як мінімум з одного вузла, який:

1. Має початковий спеціальний вузол, який називають коренем усього дерева.
2. Інші вузли знаходяться в кількості, відмінному від нуля, попарно непересічних підмножин, при цьому вони теж є деревом. Всі такі форми організації називають піддеревами головного дерева.

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

Навіщо вона застосовується в програмуванні?

Своє застосування рекурсія в програмуванні знайшла у вирішенні цілого ряду складних завдань. Якщо необхідно зробити тільки один виклик, то більш легким є застосування інтеграційного циклу, але при двох і більше повторах, щоб уникнути побудови ланцюжка і зробити їх виконання у вигляді дерева, і застосовуються рекурсивні ситуації. Для широкого класу задач організація обчислювального процесу таким способом є найбільш оптимальною з точки зору споживання ресурсів. Так, рекурсія в "Паскалі" або іншому будь-якому високорівневої мові програмування являє собою виклик функції або процедури до виконання умов, незалежно від кількості зовнішніх викликів. Іншими словами, у програмі може бути тільки одне звернення до підпрограми, але відбуватися воно буде до певного заздалегідь моменту. До певної міри це аналог циклу зі своєю специфікою використання.

Відмінності рекурсії в різних мовах програмування

Незважаючи на загальну схему реалізації та конкретне застосування в кожному окремому випадку, рекурсія в програмуванні має свої особливості. Це може призвести до складності під час пошуку необхідного матеріалу. Але завжди слід пам'ятати: якщо мова програмування викликає функції або процедури, значить, і виклик рекурсії - справа здійсненне. Але найбільш значущі її відмінності проявляються при використанні низьких і високих мов програмування. Особливо це стосується можливостей програмної реалізації. Виконання в кінцевому підсумку залежить від того, яке завдання поставлено, відповідно до неї і пишеться рекурсія. Функції та процедури використовуються різні, але їх мета завжди одна - змусити викликати самих себе.

Рекурсія - це легко. Як просто запам'ятати зміст статті?

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