Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
|
В ЫВОДЫ Рекурсия – это эффективный способ создания изящных и эффективных программ, основанный на альтернативном по отношению к циклам способе повторного выполнения кода. Рекурсивные программы и структуры данных весьма привлекательны, поскольку часто они предоставляют индуктивные аргументы, которые помогают убедиться в правильности и эффективности разработанных программ. Следует, однако, иметь в виду, что применение рекурсии сопряжено с опасностью возникновения ошибок, ведущих к экспо- ненциальному увеличению количества вызовов функций или недопустимо большой степени вложенности. Поэтому во всех тех случаях, когда сущест- вует очевидное итеративное решение задачи, следует избегать применения рекурсии. 3 / 23 73 Существует обширный класс задач, для которых применение рекурсии принципиально необходимо. К их числу относятся задачи искусственного интеллекта, связанные с поиском решений, оптимальных по тем или иным критериям. Примеры подобных задач были представлены в данной главе. У ПРАЖНЕНИЯ 1. Напишите рекурсивный алгоритм получения всех возможных пере- становок N целых чисел. 2. Напишите рекурсивную функцию, проверяющую правильность рас- становки скобок в строке. При правильной расстановке выполняются условия: − количество открывающих и закрывающих скобок равно; − внутри любой пары «открывающая – соответствующая закрываю- щая скобка» скобки расставлены правильно. 3. Создайте функцию, печатающую все возможные представления на- турального числа N в виде суммы других натуральных чисел. 4. Дано натуральное число N>1. Предложите рекурсивный алгоритм проверки, является ли оно простым. Алгоритм должен иметь слож- ность O(logN). 5. Дано слово, состоящее только из строчных латинских букв. Проверь- те, является ли это слово палиндромом. 4 / 23 |
