Непейвода Н.Н. Программирование. Раздел 3

Непейвода Н.Н. Программирование. Страница 366

8.7.1. Сопоставление итеративной и рекурсивной схем

Главная цель сопоставления двух схем программирования заключает­ся в решении вопроса о том, когда в реальных программах использовать

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

Как правило, рекурсивные программы, с точки зрения расхода времени и памяти, менее эффективны, чем итеративные: вопервых, каждое поро­ждение экземпляра связано с отведением для него определенной памяти, а вовторых, алгоритмически обусловленное время вычислений увеличива­ется за счет затрат на организацию вызова подпрограммы и возврата из нее, и хотя некоторые вычислительные машины осуществляют эти действия на аппаратном уровне (и, как следствие, делают работу с подпрограммами оп­тимальной), далеко не все архитектуры машин допускают такую поддержку процедурного механизма.

Вместе с тем, рекурсивный алгоритм во многих случаях проще и нагляд­нее, чем итеративный, особенно когда имеется рекуррентное соотношение, определяющее задачу (приведенный пример служит тому иллюстрацией). Может оказаться, что задача рекурсивна по существу, т. е. для ее решения удобнее всего воспользоваться алгоритмом с порождением вычислительных процессов, подчиненных стековой дисциплине. Итеративное описание та­кого алгоритма, как правило, будет завуалированной рекурсией, и потому разумно сразу же составлять рекурсивную программу.

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама