Программирование. Рекурсия Pascal-Паскаль
Софт. Программы для компьютера. Для пк

В С функции могут вызывать сами себя. Функция является рекурсивной, если оператор в теле функции вызывает функцию, содержащую данный оператор. Иногда называемая круговым определением, рекурсия является процессом определения чего-либо с использованием самой себя. Простым примером является функция factr , вычисляющая факториал целого числа. Факториал числа N является произведением чисел от 1 до N.

Как factr , так и его итеративный эквивалент показаны ниже: Действие нерекурсивной версии fact должно быть совершенно очевидно. Она использует цикл, начиная с 1 и заканчивая указанным числом, последовательно перемножая каждое число на ранее полученное произведение. Действие рекурсивной функции factr немного более сложно. Когда factr вызывается с аргументом 1, функция возвращает 1. Для вычисления этого значения factr вызывается с n Это происходит, пока n не станет равно 1.

При вычислении факториала числа 2, первый вызов factr приводит ко второму вызову с аргументом 1. Данный вызов возвращает 1, после чего результат умножается на 2 исходное значение n. Можно попробовать вставить printf в factr для демонстрации уровней и промежуточных ответов каждого вызова. Когда функция вызывает сама себя, в стеке выделяется место для новых локальных переменных и параметров.

Примеры рекурсивного программирования

Код функции работает с данными переменными. Рекурсивный вызов не создает новую копию функции.

Примеры рекурсивного программирования

Новыми являются только аргументы. Поскольку каждая рекурсивно вызванная функция завершает работу, то старые локальные переменные и параметры удаляются из стека и выполнение продолжается с точки, в которой было обращение внутри этой же функции. Рекурсивные функции вкладываются одна в другую как элементы подзорной трубы.

Рекурсивные версии большинства подпрограмм могут выполняться немного медленнее, чем их итеративные эквиваленты, поскольку к необходимым действиям добавляются вызовы функций. Но в большинстве случаев это не имеет значения.

Рекурсия в программировании. Анализ алгоритмов

Много рекурсивных вызовов в функции может привести к переполнению стека. Поскольку местом для хранения параметров и локальных переменных функции является стек и каждый новый вызов создает новую копию переменных, пространство стека может исчерпаться. Если это произойдет, то возникнет ошибка - переполнение стека.

Основным преимуществом применения рекурсивных функций является использование их для более простого создания версии некоторых алгоритмов по сравнению с итеративными эквивалентами. Например, сортирующий алгоритм Quicksort достаточно трудно реализовать итеративным способом. Некоторые проблемы, особенно связанные с искусственным интеллектом, также используют рекурсивные алгоритмы.

Наконец, некоторым людям кажется, что думать рекурсивно гораздо легче, чем итеративно. При написании рекурсивных функций следует иметь оператор if, чтобы заставить функцию вернуться без рекурсивного вызова.

Рекурсия

Если это не сделать, то, однажды вызвав функцию, выйти из нее будет невозможно. Это наиболее типичная ошибка, связанная с написанием рекурсивных функций. Надо использовать при разработке функции printf и getchar , чтобы можно было узнать, что происходит, и прекратить выполнение в случае обнаружения ошибки. Разделы Обзор языка С Переменные, константы, операторы и выражения Операторы управления программой Функции Оператор return Правила видимости для функций Аргументы функции Аргументы функции MAIN Функции, возвращающие нецелые значения Использование прототипов функции Возврат указателей Рекурсия Сопоставление классического и современного объявления параметров Указатели на функции Особенности реализации Массивы Указатели Структуры, объединения и определяемые пользователем типы Ввод, вывод, потоки и файлы Препроцессор и комментарии.

Опубликовано в рубрике Hd audio
Twitter Delicious Facebook Digg Stumbleupon Favorites More
  • Прикрепленное видео

Все права защищены. © 2001 toozza.ru