Вступ у використання рекурсії в C++

1. Вступ

Загалом, рекурсія значить самоповторюваний шаблон. В математиці це може бути функція визначена через себе. Інакше кажучи, це функція, що викликає сама себе. Кожна рекурсивна функція має умову завершення; інакше вона буде викликати себе безперестанку, і ця умова може бути названою базова умова.
Зазвичай, рекурсія це трошки складна для розуміння більшості студентів концепція.

2. Типи рекурсії

В C++, типи рекурсії можна визначити більш ніж за одним виміром. З одного боку, їх можна категоризувати як рекурсії часц виконання і як рекурсії часу компіляції через використання шаблонів. Рекурсії часу вионання найбільш уживана техніка в С++. Вона може бути здійснена через функції (функції члени), які викликають самі себе.
В C++, ми також можемо реалізувати рекурсії часу компіляції за допомогою шаблонів. Коли ви інстанціюєте класс (або структуру) шаблон в С++, компілятор створиює код цього класу під час компіляції. Як і рекурсії часу виконання, клас шаблон може інстанціонувати себе самого для забезпечення рекурсії. Так само потрібна умова завершення; інакше інстанціонування триватиме безупинно, щонайменше теоретично, хоча звісно в дійсності цей процес обмежений ресурсами комп’ютера і компілятора. В такому шаблоні, ви можете визначити умову завершення (базову умову) за допомогою спеціалізації шаблона або часткової спеціалізації, залежно від умови завершення.
Дехто може подумати, що він зможе реалізувати рекурсію за допомогою макросов препроцесора С++, бо вони теж заміняються під час компіляції. Насправді, препроцесор заміняє макроси ще перед компіляцією. Також препроцесор має багато обмежень; через просту заміну тексту, тут немає визначення символу зневадження для зневаджувача, але найбільш критичне обмеження те, що макроси не можуть викликати себе рекурсивно; тож ви не можете програмували рекурсії за допомогою макросів, накшталт мета-програмуванню.
Інший погляд на рекурсію це погляд на те як реалізован алгоритм рекурсії. Алгоритм рекурсії може бути реалізовним більш ніж одним способом. Можливі варіанти рекурсії це лінійна, хвостова, обопільна, двійкова і вкладена. Ви можете здійснити їх або під час компіляції через використання шаблонів або під час виконання через використання функцій або функцій членів.
Наступна діаграма показує різні типи рекурсії в залежності від їх реалізації.

Зараз ви зможете дослідити різні типи алгоритмів один за одним і побачити їх реалізації часу виконання і часу компіляції.

3. Лінійна рекурсія

Лінійна рекурсія це найпростіший вид рекурсії і можливо найбільш вживана рекурсія. В цій рекурсії, одна функція просто викликає себе доти, доки не досягне умови завершення (також відомої як базова умова); цей процес відомий як намотування. Як тільки виконана умова завершення, виконання програми повертається до викликальника; це зветься розмотуванням.
Впродовж намотування і розмотування функція може виконувати якісь додаткові корисні задачі; у випадку факторіала вона множить вхідне значення на значення повернуте під час фази розмотування. Цей процес може бути зображений у вигляді наступної діаграми (знизу), яка показує обидві фази функції обчислення факторіала із використанням лінійної рекурсії.

Математично, ви можете написати функцію обчислення факторіала таким чином; інакше кажучи, коли значення “n” нуль, повертати одинцю і, коли значення “n” більше ніж нуль, викликати функцію рекурсивно з “n-1″ і помножити результат на “n”.

int Factorial(int no)
{
  // перевірка на помилковий параметр
  if (no < 0)
  return -1;

  // умова завершення
  if (0 == no)
  return 1;

  // лінійний рекурсивний виклик
  return no * Factorial(no - 1);
}

Програма 1: Приклад лінійної рекурсії часу виконання
Попередня програма являє собою реалізацію лінійної рекурсії часу виконання. Тут ми маємо умову завершення у вигляді 0; програма починає виконувати розмотування коли досягає умови завершення. В цій програмі присутня перевірка на введення від’ємного числа, яке могло б спричините нескінченну рекурсію. Ця функція просто поверне -1 як помилку якщо параметр від’ємний.

template <int No>
struct Factorial{
   // лінійний рекурсивний виклик
   enum { value = No * Factorial<No - 1>::value };
};
// умова завершення
template <>
struct Factorial<0>
{
   enum { value = 1 };
};

Програма 2: Приклад лінійної рекурсії часу компіляції
Ця програма є прикладом лінійної рекурсії під час компіляції. Тут ми використовуємо інстанціонування шаблона для здійснення рекурсії. Також ми маємо умову завершення у вигляді спеціалізації шаблона. Це дуже простий приклад спеціалізації шаблонів і в ньому немає багато коду, але в деяких випадках вам доведеться переписати весь код у спеціалізації класу (або структури) шаблона, бо ви не можете успадкувати код з класу (або структури) шаблона для його спеціалізації.
Тут навіть не треба вводити перевірку на помилкове введення, бо програма просто не скомпілюється, якщо хтось спробує подати від’ємне число. Це дуже велика перевага рекурсії часу компіляції, що ви навіть не зможете скомпілювати нескінченну рекурсію. Однак, повідомлення про помилку може бути не зовсім зрозумілим.
Приклади використання рекурсії часу компіляції.

  cout << Factorial::value  << endl;
  cout << Factorial::value  << endl;
  cout << Factorial::value << endl;

Компілятор відмовиться скомпілювати останнє ствердження і видасть довге повідомлення про помилку.

4. Хвостова рекурсія

Хвостова рекурсія це спеціальна форма лінійної рекурсії, де рекурсивний виклик зазвичай іде останнім у функції. Цей тип рекурсії здебільшого більш ефективний, бо розумні компілятори автоматично перетворять таку рекурсію в цикл задля уникнення вкладених викликів функцій. Через те, що рекурсивний виклик функції зазвичай останнє, що робить функція, вона не має потреби ще щось робити під час розмотування; натомість, вона просто повертає значення отримане через рекурсивний виклик. Ось приклад тої самої програми реалізованої як хвостова рекурсія.

Ви можете визначити хвостову рекурсію математично через наступну формулу; інакше кажучи, коли значення “n” нуль, просто повернути значення “a”; якщо значення “n” більше ніж нуль, викликати рекурсивну функцію з параметрами “n-1″ і “n*a”. Також, можна зауважити, що під час фази розмотування кожна рекурсивно викликана функція просто просто повертає значення “a”.

int Factorial(int no, int a)
{
   // перевірка на помилковий параметр
   if (no < 0)
      return -1;

   // умова завершення
   if (0 == no || 1 == no)
      return a;

   // хвостовий рекурсивний виклик
   return Factorial(no - 1, no * a);
}

Програма 3: Приклад хвостової рекурсії часу виконання
Це змінена версія програми з лінійною рекурсією. Ви виконуєте всі обчислення до виклику рекурсивної функції, і просто повертаєте значення отримане з цього виклику. Тут, порядок обчислення зворотній до порядку за лінійної рекурсії. У випадку лінійної рекурсії, ви спочатку множите 1 на 2; отриманий результат на 3 і так далі. З іншого боку, тут ви множите n на n-1, і тоді на n-2 доки не досягнете 0.

template <int No, int a>
struct Factorial{
   // хвостовий рекурсивний виклик
   enum { value = Factorial<No - 1, No * a>::value };
};
// умова завершення
template <int a>
struct Factorial<0, a>
{
   enum { value = a };
};

Програма 4: Приклад хвостової рекурсії часу компіляції
Ось версія рекурсії часу компіляції тої самої програми, вона виконує те саме під час компіляції.
Хвостова рекурсія дуже корисна і часом неуникна в функціональниї мовах програмування, бо деякі з них можуть не підтримувати циклічні конструкції. Тоді, зазвичай, цикли реалізуються за допомогою хвостової рекурсії. За допомогою хвостової рекурсії ви можете робити майже все, що можна зробити з циклом, але в зворотньому напрямку це часто не вірно. От дуже простий приклад, що демонструє цикл через хвостову рекурсію.

// реалізація циклу через хвостову рекурсію
// проста версія
void RecursiveLoop(int n)
{
   // умова завершення
   if (0 == n)
      return;

   // дія
   cout << n << endl;

   // хвостовий рекурсивний виклик
   return RecursiveLoop(--n);
}

Програма 5: Демонстрація реалізації циклу через хвостову рекурсію, проста версія
Але ця програма виглядає дуже жорсткою і ви не можете налаштувати її. Ось змінений варіант цієї програми, в якому за допомогою шаблонів і функціональних об’єктів, ви зможете налаштовувати програму під свої потреби.

// реалізація циклу через хвостову рекурсію
// шаблонна версія
template <typename TType, typename TTerminate, typename TAction,
          typename TStep>
void RecursiveLoop(TType n)
{
   // умова завершення
   if (TTerminate()(n))
      return;

   // дія
   TAction()(n);

   // хвостовий рекурсивний виклик
   return RecursiveLoop<TType, TTerminate, TAction,
                        TStep>(TStep()(n));
}

Програма 6: Демонстрація реалізації циклу через хвостову рекурсію, шаблонна версія
Ось реалізації “Умови завершення”, “Дії”, та “Крокування циклом”.

// умова завершення визначена користувачем
template <typename T>
class IsTerminate{
public:
   // оператори визначені в цій функції
   // мають бути перевантаженими для даного типу T bool operator () (T n)
   {
      return n == 0 ? true : false;
   }
};
// умова переходу на наступний крок визначена користувачем
template <typename T>
class Step{
public:
   // оператори визначені в цій функції
   // мають бути перевантаженими для даного типу T T operator () (T n)
   {
      return --n;
   }
};
// дія визначена користувачем
template <typename T>
class Action{
public:
   // оператори визначені в цій функції
   // мають бути перевантаженими для даного типу T void operator () (T n)
   {
      cout << n << endl;
   }
};

Програма 6: Реалізація кожного кроку для рекурсивного циклу через шаблонну версію хвостовою рекурсії.
Ось простий приклад використання цієї функції.

// реалізація циклу через хвостову рекурсію
// шаблонна версія
RecursiveLoop, Action, Step >(10);

Ви не можете надати реалізацію за умовчанням у функції “RecursiveLoop”, бо С++ не дозволяє параметр за замовчанням для шаблонів функцій. Ви можете робити це тільки у випадку класів С++. З метою подолання цього обмеження ви можете використати функціональні об’єкти замість простих функцій і передати дію за замовчанням як параметр за замовченням, тож виклик буде значно простіший. Подаємо переглянуту версію цієї програми.

template <typename TType,
   typename TTerminate = IsTerminate<TType>,
   typename TAction = Action<TType>,
   typename TStep = Step<TType>
>
class RecursiveLoop{
public:
   void operator ()(TType n)
   {
      // умова завершення
      if (TTerminate()(n))
         return;

      // дія
      TAction()(n);

      // хвостовий рекурсивний виклик
      return RecursiveLoop<TType, TTerminate, TAction,
                           TStep>()(TStep()(n));
   }
};

Програма 7: Реалізація циклу через хвостову рекурсію із використанням функціональних об’єктів і параметра шаблона за замовчанням.
Відтак, використання цього функціонального об’єкта дуже просте.

RecursiveLoop()(10);

5. Обопільна рекурсія
Обопільна рекурсія також відома як непряма рекурсія. В цьому типі рекурсії, дві або більше функції викликають одна одну циклічно. Це єдиний шлях для здійснення рекурсії в мовах, що не дозволяють вам викликати функції рекурсивно. Умова завершення в такій рекурсії може знаходитись в одній або всіх функціях.

Математично, ви можете визначити ці функції як

bool isEven(int no)
{
   // умова завершення
   if (0 == no)
      return true;
   else
      // взаємний рекурсивний виклик
      return isOdd(no - 1);
}

bool isOdd(int no)
{
   // умова завершення
   if (0 == no)
      return false;
   else
      // взаємний рекурсивний виклик
      return isEven(no - 1);
}

Програма 8: Приклад обопільної рекурсії часу виконання
Це дуже примітивний приклад обопільної рекурсії. Ви знаєте, що нуль це парне число, одиниця непарне. Якщо ви хочете дізнатися чи парне число, ви можете використати ці функції; на внутрішньому рівні вони викликають одна одну і віднімають одиницю з вхідного значення доки не досягнуть виконання базової умови. Звісно, це не найліпший шлях для реалізації цього алгоритму; тут потрібна велика кількість ресурсів для визначення чи число парне. Крім того, якщо передати від’ємне число, функції будуть викликати одна одну доки не відбудеться переповнення стека.

template <int no>
struct isEven{
   // взаємний рекурсивний виклик
   enum { value = no == 0 ? 1 : isOdd<no - 1>::value };
};
// умова завершення
template <>
struct isEven<0>
{
   enum { value = 1 };
};

template <int no>
struct isOdd{
   // взаємний рекурсивний виклик
   enum { value = no == 0 ? 0 : isEven<no - 1>::value };
};
// умова завершення
template <>
struct isOdd<0>
{
   enum { value = 0 };
};

Програма 9: Приклад обопільної рекурсії часу компіляції
Ось версія програми із рекурсією часу компіляції. Єдина відмінність між програмами полягає в тому, що приклад часу компіляції навіть не скомпілюється за умови передачі від’ємного числа.
Визначення парності числа за допомогою обопільної рекурсії не дуже добра ідея. Більш цікавим прикладом є чоловіча і жіноча послідовності. Обидві функції рекурсивно викликають одна одну і можуть представлені так.


Наведемо приклади часу виконання і часу компіляції чоловічої і жіночої функцій із використанням обопільної рекурсії.

int MaleSequence(int n)
{
   // умова завершення
   if (0 == n)
      return 0;

   // взаємний рекурсивний виклик
   return n - FemaleSequence(MaleSequence(n-1));
}
int FemaleSequence(int n)
{
   // умова завершення
   if (0 == n)
      return 1;

   // взаємний рекурсивний виклик
   return n - MaleSequence(FemaleSequence(n-1));
}

Програма 10: Реалізація часу виконання Male і Female функцій,.

template <int n>
struct MaleSequence{
   // взаємний рекурсивний виклик
   enum { value = n - FemaleSequence<MaleSequence<n - 1>
          ::value>::value };
};
// умова завершення
template <>
struct MaleSequence<0>
{
   enum { value = 0 };
};

template <int n>
struct FemaleSequence{
   // взаємний рекурсивний виклик
   enum { value = n - MaleSequence<FemaleSequence<n - 1>
          ::value>::value };
};
// умова завершення
template <>
struct FemaleSequence<0>
{
   enum { value = 1 };
};

Як і з іншими функціями часу виконання, ви маєте зробити спеціалізацію шаблона для обох функцій з метою опрацювання умови завершення.
6. Двійкова рекурсія
У випадку двійкової рекурсії функція викликає себе двічі, замість одного разу. Такий тип рекурсії дуже корисний при роботі з деякими структурами даних, наприклад при обході дерева в прямому, зворотньому або центрованому порядку або генерації чисел Фібоначчі і так далі.
Двійкова рекурсія це особлива форма експонентної рекурсії, де одна функція викликає себе більш ніж один раз (у випадку двійкової рекурсій).

Математично ви можете визначити послідовність Фібоначчі як

int Fib(int no)
{
   // перевірка на помилковий параметр
   if (no < 1)
      return -1;

   // умова завершення
   if (1 == no || 2 == no)
      return 1;

   // подвійний рекурсивний виклик
   return Fib(no - 1) + Fib(no - 2);
}

Програма 12: Приклад часу виконання двійкової рекурсії
Ось проста реалізація послідовності Фібоначчі, що викликає рекурсивну функцію двічі. Тут ми маємо два базові випадкі; коли значення параметру на вході є 1 чи 2. Це, звісно, не найкраща реалізація послідовності Фібоначчі і ви можете перетворити її в хвостову рекурсію трошки змівнив її. Але, перед перетворенням її в хвостову рекурсію, погляньте на версію часу компіляції двійкової рекурсії.

template <int n>
struct Fib{
   // подвійний рекурсивний виклик
   enum { value = Fib<n - 1>::value + Fib<n - 2>::value };
};
// умова завершення
template<>
struct Fib<2>
{
   enum { value = 1 };
};
// умова завершення
template <>
struct Fib<1>
{
   enum { value = 1 };
};

Програма 13: Приклад часу компіляції двійкової рекурсії
У версії часу компіляції двійкової рекурсії, ви двічі спеціалізуєте клас шаблон (або структуру). Загалом, ви маєте робити спеціалізацію шаблона для кожного базового випадку.

int Fib(int n, int a = 0, int b = 1)
{
   // умова завершення
   if (1 == n)
      return b;
   else
      // хвостовий рекурсивний виклик
      return Fib(n-1, b, a+b);
}

Програма 14: Приклад часу виконання перетворення двійкової рекурсії в хвостову
Тут ви перетворюєте двійкову рекурсію в хвостову. Ви просто робите обчислення перед рекурсивним викликом; звідси, ви не маєте двічі робити рекурсивний виклик.
Математично це можна виразити як

template <int n, int a = 0, int b = 1>
struct Fib{
   // хвостовий рекурсивний виклик
   enum { value = Fib<n-1, b, (a+b)>::value };
};
// умова завершення
template<int a, int b>
struct Fib<1, a, b>
{
   enum { value = b };
};

Програма 15: Приклад часу компіляції перетворення двійкової рекурсії в хвостову
У версії часу компіляції ми маємо лише одну умову завершення (базову умову); тож ми потребуємо лише одну спеціалізацію шаблона. Тут робиться часткова спеціалізація, бо нас цікавить останнє обчислене значення в базовому випадку, коли n дорівнює 1.
7. Вкладена рекурсія
Це особливий тип рекурсії, коли рекурсивні виклики вкладені. В усіх попередніх типах рекурсії, ви можете замінити рекурсію на простий цикл або цикл зі стеком, але цей тип рекурсії не може бути легко замінений на простий цикл.
Типовим прикладом вкладеної рекурсії є функція Акермана.
Математично функція Акермана може бути визначена як

int Ackermann(int m, int n)
{
   // перевірка параметрів
   if (m < 0 || n < 0)
      return -1;

   // умова завершення
   if (0 == m)
      return n + 1;

   // лінійний рекурсивний виклик
   else if (m > 0 && 0 == n)
      return Ackermann(m-1, 1);

   // вкладений рекурсивний виклик
   else
      return Ackermann(m-1, Ackermann(m, n-1));
}

Програма 16: Приклад вкладеної рекурсії часу виконання
Ця функція має дві умови завершення;; одна умова припиняє вкладені виклики і починає лінійну рекурсію; друга умова завершення припиняє лінійну рекурсію. На початку розташована перевірка на допустимість параметрів.

template <int m, int n>
struct Ackermann{
   // вкладений рекурсивний виклик
   enum { value = Ackermann<m-1, Ackermann<m, n-1>
          ::value>::value };
};

template <int m>
struct Ackermann<m, 0>
{
   // лінійний рекурсивний виклик
   enum { value = Ackermann<m-1, 1>::value };
};
// умова завершення
template <int n>
struct Ackermann<0, n>
{
   enum { value = n + 1 };
};

Програма 17: Приклад вкладеної рекурсії часу компіляції
У випадку програми часу компіляції ви маєте реалізувати дві спеціалізації шаблонів через наявність двох умов завершення. Перша спеціалізація зупиняє вкладені виклики і починає лінійну рекурсію; друга зупиняє лінійну рекурсію.
Вихідна стаття