НОУ ІНТУІТ, Лекція, Рекурсія та дерева
Корова, що сміється, зображена на фірмовому жетоні "Корова, що сміється", носить як сережок фірмові жетони, на яких, я підозрюю, але зір не дозволяє переконатися в правильності мого припущення, зображена корова з фірмовими жетонами, на яких зображена … (сподіваюся, ідея зрозуміла ) 1 У нас відомий рекурсивний віршик, що увійшов у приказку: "У попа був собака, він його любив. Вона з'їла шматок м'яса, він її вбив, і в землю закопав, і на могилі написав, що у попа був собака ...".
Рекурсивне визначення
"Рекурсія" - використання рекурсивного визначення - широко застосовується в програмуванні: вона дозволяє елегантно визначати синтаксичні структури; ми також ознайомимося з рекурсивно визначенимиструктурами данихта рекурсивнимипроцедурами.
Ми будемо використовувати термін"рекурсивний"як скорочення "рекурсивно визначений" - рекурсивна граматика, рекурсивна структура даних. Але це лише угода, оскільки не можна сказати, що поняття чи структура власними силами рекурсивні. Все, що ми знаємо – це те, що їх можна рекурсивно описати відповідно до вищенаведеного визначення. Будь-яке часткове поняття – у тому числі структура, що задає корову, що сміється, – може бути визначено як рекурсивно, так і без використання рекурсії.
При розгляді властивостей рекурсивно певного поняття застосовуватимемо рекурсивні докази – узагальнюючі індуктивні докази, що використовують цілі числа для індуктивного кроку.
Рекурсія є прямою , якщо визначення посилається на екземпляр , і непрямою, якщо для (для деякого =2" style="display: inline; ">) визначення кожного посилається на , а визначення посилається на .
У цій лекціїнас будуть цікавити такі поняття, для яких рекурсивні визначення природні, елегантні та зручні. Приклади включатимуть рекурсивні програми, рекурсивні синтаксичні визначення, рекурсивні структури даних. Ми також отримаємо деяке уявлення про рекурсивні докази.
Один із класів рекурсивних структур даних –деревау їх різних уявленнях – з'являються у багатьох додатках і відбивають дуже точно ідею рекурсії. У цій лекції розглядається важливий випадок бінарних дерев.
8.1. Основні приклади
У цей момент можуть виникнути цілком обґрунтовані сумніви - а чи є сенс у рекурсивних визначеннях, як можна визначити поняття через саме поняття, "олія"?
Ви маєте право сумніватися. Не всі рекурсивні визначення хороші визначення чогось. Коли вас просять дати характеристику комусь, а ви відповідаєте: "Світла? Ну, це просто Світлана, що ще можна сказати!" – то ви небагато нового сказали. Отже слід подбати про умови, що гарантують корисність визначення, навіть якщо воно рекурсивне.
Перш ніж ми це зробимо, дозвольте переконатися прагматичним шляхом, ознайомившись із декількома типовими прикладами, коли рекурсія очевидно корисна та осмислена. Це додасть нам тверду переконаність, більшу, ніж просто віра, що базується на надіях і молитвах, що рекурсія – це практично корисний спосіб визначати граматики, структури даних та алгоритми. Після чого настане час для відповідного математичного обґрунтування рекурсивних визначень.
Рекурсивні визначення
Із запровадженням універсальності ми отримуємо можливість визначати тип як: