Линейная и древовидная рекурсии

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

Пример 5. Написать рекурсивное определение возведения числа x в степень n:

Базисное утверждение: x ⁰ =1;

Рекурсивное утверждение:     xⁿ = x * xⁿ -1;

Определим 3⁵

3⁵= 3⁴*3

3⁴= 3³*3

…….

3⁰=1.

 

Рисунок 5 – Схема процесса вычисления 5 степени тройки

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

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

#include "stdafx.h"       

#include <stdio.h>

Long int funstep(int x,int n)

{

if (n==0) return 1;

else

  {

   return x*funstep(x,n-1);

}

}

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

{

int x,n;

 puts("input x,n for x^n");

scanf("%d %d",&x,&n);

 printf("\n %7d ^ %3d =",x,n);

 printf("%10d\n",funstep(x,n));

return 0;

}

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

Пример 6. Написать программу, которая вычисляет число Фибоначчи по его номеру. По определению последовательность  1 1 2 3 5 8 13 21 34 55 89 ….получила название чисел Фибоначчи. Первые два числа равны 1 (F1=1, F2=1), а остальные, начиная со второго, вычисляются по следующей схеме: Fn=Fn-1+Fn-2. Эта процедура может быть легко описана с помощью рекурсии. При этом:

Базисное утверждение: F1=1 и F2=1

Рекурсивное: Fn=Fn-1+Fn-2

Найдем значение 6-го числа Фибоначчи. Схема вычисления выглядит так:

F6=   F5                          +                       F4

F5=   F4           +          F3;                   F4=F3 +   F2;

F4=F3 + F2                F3=F2 + F1;     F3=F2 + F1    F2=1

F3=F2+F1; F2=1;             F2=1; F1=1;     F2=1; F1=1;          

 F2=1, F1=1.

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

 

     Рисунок 6 – Дерево вычисления числа Фибоначчи

Тело программы вычисления числа Фибоначчи:

#include "stdafx.h"

#include <stdio.h>

Int fib(int n)

{

if((n==1)||(n==2)) return 1;

else

{ return fib(n-1)+ fib(n-2);}

}

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

{ int n;

puts("input n value Fibonnachi");

scanf("%d",&n);

 printf("\n %7d Fibonachi =",n);

 printf("%10d\n",fib(n));

return 0;

}

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

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

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

 

Пример 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 ("%4 d \ n ", x [ i ]);

   print (x, i +1);

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

}

}

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

Задания для самопроверки

Задание 1. Разработайте рекурсивную подпрограмму, формирующую следующую последовательность строк:

A

BB

CCC

DDDD

EEEEE

FFFFFF и т. д.

Всего 26 строк.

Разработайте тестирующую программу.

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

             ì 0, если m>n³0;

с{m,n} = í 1, если (m=0 и n>0) или (m=n=0);

             î c{m-1,n-1} + C{m,n-1} в остальных случаях.

Задание 3. Разработайте рекурсивную подпрограмму быстрой сортировки элементов массива (сортировка Хоора [3, 5]). Быстрая сортировка выполняется следующим образом. Выбирают любой, например, первый элемент массива, и затем элементы переставляют так, чтобы слева располагались элементы меньше выбранного, а справа – больше. Для этого массив просматривают с двух сторон и меняют местами элементы, стоящие не в своей части массива. Тем самым выбранный элемент оказывается на своем месте. После этого описанный алгоритм применяют к левой и правой частям образовавшихся подмассивов. Процесс продолжается, пока очередной подмассив не окажется состоящим из одного элемента.

 

 Глава 2. Полный и ограниченный перебор. Использование рекурсии при программировании ограниченного перебора