Лекции по информатике - Рекурсия и итерация

Рекурсией — называется ситуация, когда программа вызывает сама себя непосредственно или косвенно (через другие функции).

Явный вызов:

Косвенный вызов: А вызывает В, В вызывает А, обе функции рекурсивны

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

Рекурсивная задача в общем случае разбивается на ряд этапов. Для решения задачи вызывается рекурсивная функция. Эта функция знает, как решать только простейшую часть задачи — так называемую базовую задачу (или несколько таких задач). Если функция вызывается для решения базовой задачи, она просто возвращает результат. Если функция вызывается для решения более сложной задачи, то она делит эту задачу на две части: одну часть, которую функция решать умеет, и ту которую решать не умеет. Чтобы сделать рекурсию выполнимой, последняя часть должна быть похожа на исходную задачу, но по сравнению с ней проще или несколько меньше. Поскольку новая задача подобна исходной, функция вызывает новую копию самой себя, чтобы начать работать над меньшей проблемой — это называется рекурсивным вызовом или шагом рекурсии. Шаг рекурсии выполняется до тех пор, пока исходное обращение функции еще не закрыто. Шаг рекурсии может приводить к большому числу таких рекурсивных вызовов, поскольку функция продолжает деление каждой новой подзадачи на две части.

Задача: написать подпрограмму решения уравнения f(x)=0, если известно, что f(x) непрерывна на [a,b] и имеет разные знаки на концах отрезка.

Далее приводится пример программы содержащей итеративный и рекурсивный метод решения этой задачи.

program test;
{$N+} {генерация кода с помощью сорпоцессора
 математических вычислений 8087}
uses crt;
type
  _Real = single;

_FR2R = function(x : _Real): _Real;

{——————————рекурсивный метод——————————————}

procedure solve(a,b : _Real;f:_FR2R; eps : _Real; var root : _Real);
{a,b - концы отрезка,f-левая часть уравнения f(x)=0,
 eps>0-точность решения, предпологается f -непрерывна и имеет
 разные знаки на концах a и b, root - найденный корень}
var
  fa,fb,fr : _Real;
begin
  fa:= f(a); { вычисление значения функции на конце отрезка }
  root := (a+b)/2.0; { деление отрезка пополам }
  fr:= f(root); { вычисление значения функции в середине отрезка }
  if fr=0.0 then exit; { если 0 то выход }
  if abs(b-a)<2.0*eps then exit; { проверка точности }
  if ((fa>0.0) and (fr<0.0)) or ((fa<0.0) and (fr>0.0)) then
  { проверка знака на концах }
    solve(a,root,f,eps,root)
  else
    solve(root,b,f,eps,root);
end;

{—————————метод итераций—————————————————}

procedure solve1(a,b:_Real;f:_FR2R; eps:_Real; var root:_Real);
var
  eps2,fa,fb,fr : _Real;
begin
  fa:=f(a); {вычисление значения функции на концах отрезка}
  fb:=f(b);
  eps2:=2.0*eps;
  while abs(b-a)>eps2 do {прерывем если погрешность меньше заданной}
  begin
    root:=(a+b)/2.0;
    fr:=f(root); {вычисление значения функции в середине}
    if fr=0 then break; {если 0 то выход из подпрограммы}
    if ((fa>0.0) and (fr<0.0)) or ((fa<0.0) and (fr>0.0)) then
    { проверка знака}
    begin
      b:=root; {переименовываем концы}
      fb:=fr;
    end else
    begin
      a:=root;
      fa:=fr;
    end;
  end;
  root := (a+b)/2.0; {уменьшения отрезка}
end;

function f1(x:_Real):_Real; far;
begin
  f1:= sqr(x)-4.0; {задание функции}
end;

function f2(x:_Real):_Real; far;
begin
  f2:=cos(x)-x; {задание функции}
end;

var
  a,b,x,eps :_Real;
begin
  clrscr;
  write('a,b,eps 1-го уравнения: ');
  readln(a,b,eps);
  solve(a,b,f1,eps,x);
  writeln('x1 = ',x);
  solve1(a,b,f1,eps,x);
  writeln('x2 = ',x);
  write('a,b,eps 2-го уравнения: ');
  readln(a,b,eps);
  solve(a,b,f2,eps,x);
  writeln('x3 = ',x);
  solve1(a,b,f1,eps,x);
  writeln('x4 = ',x);
end.

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

Задача о Ханойских башнях

Легенда гласит, что в одном из монастырей Дальнего Востока монахи пытались переместить стопку дисков с одного колышка на другой. Начальная стопка имела 64 диска, нанизанных на один колышек так, что их размеры последовательно уменьшались к вершине. Монахи пытались переместить эту стопку с этого колышка на второй при условии, что при кажлом перемещении можно брать только один диск и больший диск никогда не должен находиться над меньшим диском. Третий колышек предоставляет возможность временного размещения дисков. Считается, что когда монахи решат эту задачу наступит конец света.

Требуется чтобы программа печатала четкую последовательность перемещений дисков с колышка на колышек.

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

type
  _Name = char; {тип совместимый с выводом в текстовый файл}
  _Unsign = byte;

procedure HT(source,dest,tmp :_Name;n:_Unsign; var F:text);
{ sourece,dest,tmp - названия источника, приемника и
  вспомогательного колышка, n - число дисков, F- файл,
  открытый для записи.
  Процедура печатает список ходов,файл 
  остается открытым }
begin
  if n = 1 then
    writeln(F,source,'->',dest)
      { если диск один то сразу перемещаем 
        его на колышек приемник }
  else
  begin
    HT(source,tmp,dest,n-1,F); 
      { меняем местами вспосогательный и приемник колышки }
    writeln(F,source,'->',dest); {выводим шаг}
    HT(tmp,dest,source,n-1,F);
      { меняем местами вспомогательный и источник колышки }
  end;
end;

var
  n:_Unsign;
  f : text;
  s,d,t : _name;
  f_name : string;
begin
  write('Введите названия источника: ');
  readln(s);
  write('Введите названия приемника: ');
  readln(d);
  write('Введите названия вспомогательного диска: ');
  readln(t);
  write('Введите количество дисков: ');
  readln(n);
  assign(f,'Process.txt'); 
    { связываем файловую переменную с именем файла }
  rewrite(f); { инициируем запись в файл }
  HT(s,d,t,n,f);
end.

Как и для предыдущей задачи для доказательства правильности работы алгоритма используем метод математической индукции. Глубина стека n, число ходов 2ⁿ-1.

Слава Антонов © 2002 — August 13, 2008

197-577-902