Сравнение рекурсии и итерации

Рекурсия:

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

Итерация:

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

При выполнении сравнения можно учитывать разные критерии.

1. Самый распространенный – это эффективность алгоритма. В данном случае под эффективность понимаются время процессора и объем занятой программой (и данными) памяти. В данном случае не трудно заметить явное преимущество итеративного метода по сравнению с рекурсивным.

2. Сложность написания и отладки программы. По существу это вопрос о затратах труда программиста. Сравнение двух текстов показывает, что рекурсивная программа пишется автоматически на основе поставленной задачи, в то время как итеративная требует преобразования задачи и "изобретения" алгоритма, введение дополнительных переменных, отсутствовавших в постановке задачи, и неочевидных операций. Поэтому, с этой точки зрения, рекурсивный алгоритм предпочтительнее итеративного.

Вывод:В тех случаях, когда не требуется получать очень быстрый отклик программы, рекурсия помогает сэкономить на разработке программы.


на примере чисел Фибоначчи:

рекурсия:

function Fr(n:integer):integer;

begin if n=1 or n=2 then Fr:=1

else Fr:=Fr(n-1)+Fr(n-2);

end;

итерация:

function Fi(n:integer):integer;

var i,n1,n2,result: integer;

begin n1:=1,n2:=1;{установка начальных значений}

result:=1; {на тот случай,если n=1 или 2}

for i:=3 to n do {не выполняется если n<3}

begin result:=n1+n2; {соот-ет осн формуле чисел Фиб}

n2:=n1; {сдвиг значений на один индекс}

n1:=result;

end;

Fi:=result; {установление значения функции}

end;



9843229719996045.html
9843258675052680.html
    PR.RU™