урсивні функції при тій же кількості ітерацій, що і висхідний динамічний програмування. Технологія вимагає введення в рекурсивну програму деяких засобів, забезпечують збереження кожного обчисленого значення і перевірку збережених значень, щоб уникнути їх повторного обчислення.
Таким чином, сучасні інформаційні технології містять досить коштів, щоб зробити теоретично ефективні рекурсивні алгоритми, також ефективними і широко використовуваними на практиці.
В В В В В В В В В В В В В В
Приклад: компілятор Turbo Pascal 7.0.
Широкі можливості використання рекурсивних процедур дає середу програмування Turbo Pascal 7.0. Механізм цього процесу реалізований тут згідно з загальними принципам - за допомогою стека.
Користувач може повністю контролювати перетворення даних в стеці, поява і завершення рекурсивних викликів, для чого натисканням клавіш Ctrl + F3 відкривається вікно В«Call StackВ». У ньому міститься вся інформація про поточний стан стека.
Розмір стека за замовчуванням - 16 Кб, а максимальний розмір - 64Кб. Якщо незавершених рекурсивних викликів занадто багато (помилково в програмі може виникнути і нескінченної рекурсією), то система видасть повідомлення В«Stack overflow В»(В« Переповнення стека В»). Це одна з найпоширеніших помилок при програмуванні рекурсивних алгоритмів. У першу чергу необхідно перевірити рекурсію, використовувану в програмі, на наявність умови завершення (так званої базової завдання), щоб переконатися у відсутності нескінченної рекурсії. В інших випадках є сенс збільшити розмір стека, використовуючи меню В«Options | Memory Sizes".
При необхідності можна маніпулювати стеком за допомогою директиви компілятора $ M, яка містить три параметри. Розмір стека визначається першим параметром директиви. Другий і третій її параметри - нижня і верхня межі області динамічно виділеної пам'яті (купи, heap). Однак потрібно пам'ятати, що ці установки будуть діяти тільки для даної програми.
Сам рекурсивних виклик здійснюється за звичайними синтаксичним правилам виклику підпрограм. p> Бачимо, що використання рекурсії стало простим і зрозумілим. Це створює додатковий стимул для активного її застосування в практичному програмуванні.
В
Висновок.
За підсумками різнобічного дослідження рекурсивних алгоритмів можна зробити ряд важливих і, треба сказати, приємних висновків.
перше, рекурсивні алгоритми є універсальний засіб вирішення різноманітних алгоритмічних проблем. Показано, що будь-яка здійсненне завдання такого роду має рекурсивне рішення, яке при цьому відрізняється витонченістю і простотою для сприйняття людиною.
друге, рекурсивні алгоритми часто мають більш низьку асимптотическую складність, ніж еквівалентні їм ітераційні. Тобто теоретично вони швидше. p> третє, розвиток сучасних програмних засобів зробило практичне використання рекурсії досить нескладно...
