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

Відео: Програмування на Python

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

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

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

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

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

Відео: Pascal (Урок 14) Рекурсія

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

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

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

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

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

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

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

Відео: 9. CS50 російською: Лекція # 9 [Гарвард, Основи програмування, осінь 2015 рік]

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

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

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

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

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

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