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

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

 

Пример 7. Определение корней уравнения y=x²-2 на заданном отрезке методом половинного деления.

Для простоты будем считать, что отрезок задается таким образом, что корень на нем есть (иначе основная программа должна содержать проверку наличия корня).

Метод половинного деления для непрерывных функций заключается в следующем:

Базисное утверждение: Если абсолютная величина функции в середине отрезка не превышает заданного значения точности, то координата середины отрезка и есть корень.

  Рекурсивное утверждение: Корень расположен между серединой отрезка и тем концом, значение функции в котором по знаку не совпадает со значением функции в середине отрезка.

Рисунок 7 – Схема алгоритма рекурсивной программы-процедуры вычисления корня функции на отрезке

Текст программы:

#include "stdafx.h"

#include <stdio.h>

#include <math.h>

void root(float a,float b,float eps,float &r)

{

float x,f;

x=(a+b)/2;

f=x*x-1;

 if (fabs(f)>=eps)

     if ((a*a-1)*f>0)

                root(x,b,eps,r);

     else

              root(a,x,eps,r);

else

     r=x;

}

 

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

Пример 8. Проверка чередования букв и цифр в заданной строке (первый символ - обязательно буква).

 Базисные утверждения: Строка допустима, если она пустая.

                                          Строка не допустима, если обнаружен не допустимый символ.

Рекурсивное утверждение: Если текущий символ строки допустим, то допустимость строки определяется оставшейся частью строки.

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

 Текст программы:

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

bool f_char(char st[]);

bool f_value(char st[])

{ if(strlen(st)==0)

return true;

else

{

     if((st[0]<='9')&&(st[0]>='0'))

     {

             int l=strlen(st);char s[40];

     strncpy(s,&st[1],l-1);s[l-1]='\0';

     return f_char(s);

     }

     else return false;

}

}

bool f_char(char st[])

{

if(strlen(st)==0)

  return true;

   else

   {

     if((st[0]<='Z')&&(st[0]>='A'))

     {

                int l=strlen(st);char s[40];

        strncpy(s,&st[1],l-1);s[l-1]='\0';

          return f_value(s);

     }

     else return false;

}

}

int main(int argc, char* argv[])

{  

char s[40];

puts("input string char and value");

 scanf("%s",s);

if (f_char(s))

      printf("\n TRUE\n");

else   

    printf("\n FALSE\n");

return 0;

}

Данная программа разработана не совсем удачно, так как размер фрейма активации достаточно большой. Это объясняется тем, что используется вспомогательный локальный параметр - строка, размер которой 40 байт. Так как она создается в стеке, то каждая активация использует эти дополнительные байты. И чем больше строка, тем больше памяти в стеке будет использовано. Например, если длина строки 10 символов, то количество активаций будет 11, а значит, фрейм активации будет не меньше 440 байт.   Для уменьшения размера фрейма следует подумать об изменении способа передачи параметра. Действительно, если гарантировать, что исходная строка изменяться не будет, то ее можно передавать по указателю. Переход к следующему символу можно осуществить, используя дополнительный указатель (4 байта в основной программе) и адресную арифметику. Размер фрейма активации при этом сократится и будет составлять»10байт.

Текст программы:

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

bool f_char(char * st);

bool f_value(char * st)

{

if(strlen(st)==0)

    return true;

else

{

     if((st[0]<='9')&&(st[0]>='0'))

              return f_char(++st);

     else

                   return false;

   }

}

bool f_char(char * st)

{

 if(strlen(st)==0)

return true;

else

{

     if((st[0]<='Z')&&(st[0]>='A'))

              return f_value(++st);

     else return false;

}

}

int main(int argc, char* argv[])

{ char s[80],*ptr;

puts("input string char and value");

      scanf("%s",s);

      ptr=s;

      if (f_char(ptr))

      printf("\n TRUE\n");

      else printf("\n FALSE\n");

     return 0;

}

 

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

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

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

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

Рисунок 8 – Схема алгоритма подпрограммы с операторами после рекурсивного вызова

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

то она будет выглядеть так, как показано на рисунке 9.

 

                                    

Рисунок 9 – Схема последовательности обработки операторов рекурсивной подпрограммы

Таким образом, сначала выполняются операторы до вызова всех активаций. Затем, при достижении условия выхода, выполняется нерекурсивная часть. И только потом, в порядке, обратном порядку вызова, операторы, записанные после рекурсивного вызова (!!!). Используя это свойство, построим обработку следующим образом: в области до вызова запрограммируем печать положительных чисел, в области после вызова - печать отрицательных чисел, а нерекурсивная часть будет содержать вывод звездочек.

Тескт программы:

#include "stdafx.h"

#include <stdio.h>

// рекурсивная подпрограмма

void print(int x[],int i)

{

if (x[i]==0) puts("***********");

else

{

if (x[i]>0)printf("%4d\n",x[i]);

   print(x,i+1);

if (x[i]<0)printf("%4d\n",x[i]);

}

}

Примечание. Обратите внимание, что значение i при каждом вызове свое, и оно не меняется все время обработки данного вызова: одно и то же, как до вызова, так и после него.