Рекурсия

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

Рекурсия широко применяется в математике. В качестве примера дадим рекурсивное определение суммы первых n натуральных чисел. Сумма первых n натуральных чисел равна сумме первых (n-1) натуральных чисел плюс n, а сумма первого числа равна 1. Или:

Sn=Sn-1+n, S1=1.

Опишем функцию, которая вычисляет сумму, пользуясь данным определением:

function sum(n: integer): integer;
begin
  if n=1 then sum:=1
  else sum:=sum(n-1)+n;
end;

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

Операция суммирования будет повторяться ровно n-1 раз, поскольку функция sum обращается n-1 раз к самой себе, при этом параметр каждый раз уменьшается на единицу. В конце концов параметр станет равным 1, и рекурсивные вызовы закончатся, после чего все уже вызванные функции одна за другой завершат свою работу.

Рекурсивная процедура или функция содержит всегда условие окончания

if n=1 then sum:=1

При выполнении рекурсивной ветви

else sum:=sum(n-1)+n

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

Рекурсия полезна, прежде всего, в случаях, когда основную задачу можно разделить на подзадачи, имеющие ту же структуру, что и первоначальная задача.

Не следует путать рекурсию с итерацией, которая реализуется при помощи циклов.
Большинство алгоритмов можно реализовать двумя способами: итерацией и рекурсией.

Особенности рекурсии:

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

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

Вряд ли рекурсию можно рекомендовать для нахождения суммы. Рекурсивная функция sum приведена лишь в целях иллюстрации механизма рекурсии.

Пример. Рекурсивное решение задачи разбиения натурального числа на цифры. В данном примере цифры выводятся в обратном порядке.

var n: integer;
procedure reverse(n: integer);
begin
  write(n mod 10);
  if (n div 10) <> 0 then reverse(n div 10);
end;
begin
  writeln('Введите натуральное число <= ',maxint);
  readln(n);
  reverse(n);
  readln;
end.

 

Косвенная рекурсия

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

А поскольку подпрограмма обязательно должна быть описана до ее вызова, должно использоваться опережающее описание заголовка подпрограммы. Описывается один только заголовок, вслед за которым ставится зарезервированное слово forward (опережающий), а полное описание процедуры помещается далее в тексте программы. Такое описание называется определяющим. В определяющем описании можно не указывать формальные параметры, т. к. они уже известны из опережающего описания.

Например:

var a,b: real;

procedure p1(x: real); forward;

procedure р2(у: real);
begin
…   p1(а);   …
end;
procedure p1;
begin
…   р2(а);  …
end;

begin
  р2(а);
  p1(b);
end.

Как видно из примера, опережающее описание процедуры p1 позволило использовать обращение к ней из процедуры р2, т.к. при трансляции компилятору еще до вызова процедуры p1 из опережающего описания становятся известны ее формальные параметры, и он может правильно организовать ее вызов.

Как работает рекурсия

Самовызов процедуры ничем не отличается от вызова другой процедуры. Что происходит, если одна процедура вызывает другую:

  • в памяти размещаются параметры, передаваемые процедуре;
  • в другом месте памяти сохраняются значения внутренних переменных вызывающей процедуры;
  • запоминается адрес возврата в вызывающую процедуру;
  • управление передается вызванной процедуре;
  • Если процедуру вызвать повторно из другой процедуры или из нее самой, будет выполняться тот же код, но работать он будет с другими значениями параметров и внутренних переменных. Это и дает возможность рекурсии.

Пример. Рекурсивная процедура Power(X, N, Y) возводит число X в степень N и возвращает результат Y.

Procedure Power (X: real; N: integer; var Y: real); 
Begin 
  If N = 0 then
    Y := 1
  Else
    Begin
      Power(X, N-1, Y);
      Y := Y*X;
    End;
End;

Проследим за состоянием памяти в процессе выполнения вызова данной процедуры Power(5,3, Y).

Число копий переменных, одновременно находящихся в памяти, называется глубиной рекурсии. Как видно из примера, сначала она растет, а затем сокращается.
На этом примере видно, что для описания рекурсивного решения необходимы две четко определенные вещи:

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

Метод быстрой сортировки (сортировка Хоара)

В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается некоторое значение в качестве «основы»  и  затем  весь массив  разбивается на две части. Одну часть составляют все элементы, равные или большие «основы», а другую часть составляют все элементы меньшего значения, по которому делается разбиение. Этот процесс продолжается для оставшихся частей до тех пор, пока весь массив не будет отсортирован.

type mas=array [1..20] of integer;
var a:mas; i,n:integer;

procedure qs(l,r:integer);
var i,j,x,y:integer;
begin
  i:=l; j:=r; x:=a[(l+r) div 2];
  repeat
    while a[i] < x do i:=i+1;
    while x < a[j] do j:=j-1;
    if i <= j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; i:=i+1; j:=j-1; end; until i > j;
  if l < j then qs(l,j);
  if i < r then qs(i,r);
end;

begin
  writeln('Vvedite n');
  readln(n);
  writeln('Vvedite massiv');
  for i:=1 to n do
    readln(a[i]);
  qs(1,n);
  for i:=1 to n do
    write(a[i]:3);
  readln;
end.

 

Домашнее задание

1. Подготовить доклад на тему: «Задача «Ханойские башни»» или «Недостатки применения рекурсий».
2. Написать программы с использованием рекурсивных процедур или функций:

  • Нахождение факториала натурального числа.
  • Нахождение суммы элементов массива.
  • Написать программу ввода четных элементов и вывода их в обратном порядке. Массивы не использовать.