Функції та узагальнення

Функції є основним будівельним блоком, за допомогою якого ми створюємо програми. Вони являють собою конкретну реалізацію загального принципу розкладання на частини.

Простіше кажучи, функція — це заклинання, якому ми щось даємо (вхід), а воно повертає нам щось інше (вихід).

• Приклад із казки: збільшувальна чарівна паличка, якою ми постукуємо по овочам, і вони збільшуються вдвічі.
• Математичний приклад: функція квадратного кореня, у яку ми вводимо число, а вона повертає інше число (наприклад, якщо задамо 25, то отримаємо результат 5).
• Приклад програмування: функція polygon(n, length), якій ми надаємо два числа (кількість сторін і довжину сторони) як вхідні дані, і вона малює зображення багатокутника.

Прості функції без параметрів дозволяють лише повторне виконання точно такого самого коду (наприклад, створення квадрату завжди однакового розміру). Однак функції також можуть містити параметри, які впливають на їх поведінку (наприклад, розмір квадрата). Функції можуть викликати інші функції, а іноді навіть самі себе – такі функції називаються рекурсивними.

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

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

Приклад із повсякденного життя: Алік, Бен і Рекс — три конкретні домашні тварини. Ми можемо позначити їх абстрактним терміном «собака», тим самим нехтуючи деякими з їхніх характеристик (наприклад, віком, кольором шерсті чи породою), і ми зосереджуємося лише на тому, що вони мають спільного. Якби в нас удома ще був кіт Мурко, ми могли б для їх сукупного позначення використовувати, наприклад, категорію «ссавець».

Приклад із програмування: під час візуалізації зображень ми можемо створити функцію squareA(), яка малює синій квадрат розміром 100, і squareB(), яка намалює жовтий квадрат розміром 200. Але краще створити абстрактнішу функцію square(length, color), яка намалює квадрат будь-якого розміру тa кольору (за вказаними параметрами). Як варіант, ми можемо продовжити абстракцію далі та створити функцію, яка візуалізує будь-який багатокутник (із заданою кількістю вершин).

Функції є основним будівельним блоком, за допомогою якого ми створюємо програми. Вони являють собою конкретну реалізацію загального принципу розкладання на частини.

Простіше кажучи, функція — це заклинання, якому ми щось даємо (вхід), а воно видає нам щось інше (вихід).

• Приклад із казки: збільшувальна чарівна паличка, якою ви постукаєте по овочу, і він збільшиться вдвічі.
  • Математичний приклад: функція квадратного кореня, в яку ми вводимо число, а вона повертає інше число (наприклад, при введенні 25 отримуємо результат 5).
  • Приклад програмування: функція polygon(sides, length), у яку ми вводимо два числа (кількість сторін і довжину сторони), і вона малює зображення багатокутника.

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

Проєктування рекурсивних алгоритмів

Спочатку ми визначаємо підпроблеми, які нам потрібні для розв’язання нашої проблеми (так, щоб обчислити факторіал n, нам потрібно знати факторіал n - 1). Ми вирішуємо ці підзадачі рекурсивно (тобто, викликаючи функцію з різними параметрами) і збираємо отримане рішення з результатів. Крім того, необхідно визначити базовий варіант і його рішення (наприклад, факторіал 0 дорівнює 1). Базовий варіант має бути таким, щоб усі гілки обчислення досягали його з часом, інакше обчислення ніколи не завершиться.

Самопосилання

Рекурсія є прикладом більш загального явища посилання на себе, так званої самореференції. Самопосилання виникає у мові (можливо, це речення говорить саме за себе), книгах, театрі, кіно та математиці. Посилання на себе навіть є основною складовою, мабуть, найвідоміших доказів у математиці (теорема Геделя про неповноту), а також в інформатиці (існування проблем, для яких немає алгоритму для їх розв’язування, як-от: завдання визначити, чи дана програма коли-небудь зупиняється).

Фрактали

Поряд з рекурсією, найбільш типовим представником самопосилання є фрактали – зображення, які є самоподібними, тобто їх частини нагадують зображення в цілому. Фрактали часто можна побачити у природі (як-от, гілки дерев, папороті). Фрактали і рекурсія не є двома незалежними представниками самопосилання, між ними також існує сильний зв’язок. Рекурсія є дуже елегантним способом визначення різних фракталів. Через це ми часто можемо візуалізувати складні фрактали за допомогою простих рекурсивних функцій.