18. Още за рекурсията

 Леймър, е програмист, който пише програми
в колонка и който, като чуе за рекурсия,
получава леко разстройство.
Преслав Наков, Панайот Добриков
Непряка рекурсия.
    Ако една функция f1 вика друга функция f2, а втората функция f2 вика първата f1, казваме, че има непряка рекурсия.
     Пример. Хилбертови криви.
    Хилбертова крива от 1-ви ред H1 се получава като се чертае наляво - надолу - надясно единичната отсечка. H2 се състои от 4 криви H1 намалени наполовина, първата завъряна на +90, втората отместена на 1/2 наляво,  третата отместена на 1/2 надясно и четвъртата завъртяна на -90 градуса и отместена 1/2 надясно. По същия начин е получена и кривата от 3-ти ред H3 от H2. Процесът може да продължи с получаване на H4, H5 и т. н. Има 4 елемента A, B, C и D, от които се състои всяка крива. За да напишем рекурсията, нека предположим, че можем да чертаем тези елементи и отсечки като "костенурка-графика":
- left - наляво;
- down - надолу;
- right - надясно;
- up - нагоре
с дължини 1/n за кривата Hn.
H1 H2 H3

Получаваме следната схема на рекурсията:
A: left,  down, right -> D left  A down  A right B
B: up,    right,down  -> C up    B right B down  A
C: right, up,   left  -> B right C up    C left  D
D: down, left,  up    -> A down  D left  D up    C
Остава да се реализира "костенурка-графика", което може да се направи с познатата графична библиотека.
    Програма за чертаене на Хилбертови криви.
// hilbert.cpp
#include "ccc_win.cpp"

int h = 512;    /* дължината на "единичната" отсечка   */
int xold, yold; /* текущи координати на "костенурката" */
int x, y;       /* нови координати на "костенурката"   */

void Hilbert();
void A(int i);
void B(int i);
void C(int i);
void D(int i);

void plot()
/* ЦЕЛ: реализира "костенурка-графика" -
   чертае отсечка, свързваща точките (xold, yold) и (x,y)в
*/
{ Line l(Point(x,y), Point(xold, yold));
  cwin << l;
  xold = x;  yold = y;
}

void Hilbert()
{ int i = 0;
  int x0 = h/2, y0 = h/2;
  do
  { i++; h /= 2;
    x0 += h/2; y0 += h/2;
    xold = x = x0; yold = y = y0;
    A(i);
  }
  while (i < 5);
}

void A(int i)
{ if (i == 0) return;
  D(i-1); x -= h; plot();
  A(i-1); y -= h; plot();
  A(i-1); x += h; plot();
  B(i-1);
}
void B(int i)
{ if (i == 0) return;
  C(i-1); y += h; plot();
  B(i-1); x += h; plot();
  B(i-1); y -= h; plot();
  A(i-1);
}
void C(int i)
{ if (i == 0) return;
  B(i-1); x += h; plot();
  C(i-1); y += h; plot();
  C(i-1); x -= h; plot();
  D(i-1);
}
void D(int i)
{ if (i == 0) return;
  A(i-1); y -= h; plot();
  D(i-1); x -= h; plot();
  D(i-1); y += h; plot();
  C(i-1);
}

int main()
{ cwin.coord(0, h, h, 0);
  Hilbert();
  return 0;
}
 

Ефективност на рекурсията.
* Числа на Фибоначи.
    Рекурсията е мощен инструмент за реализиране на ефективни алгоритми. В някои случаи обаче, тя може да доведе до лошо работещи алгоритми. Такъв е случаят с алгоритъма за пресмятане на числата на Фибоначи  fi, които се дефинират рекурентно така:

f1 f2 = 1 и  fi fi - 1 fi - 2 за  i = 3, 4, ... .
Рекурсивна функция за пресмятане на n-тото число на Фибоначи се пише лесно точно по рекурентната формула. Ще измерваме и времето за работа на тази функция.
// fibtime.cpp
#include <iostream>
using namespace std;
#include "ccc_time.cpp"

long fib(int n)
{ if (n <= 2) return 1;
  else return fib(n - 1) + fib(n - 2);
}

int main()
{ cout << "Enter n: ";
  int n;
  cin >> n;
  Time before;
  long f = fib(n);
  Time after;
  cout << "fib(" << n << ") = " << f << "\n";
  cout << "Elapsed time = " << after.seconds_from(before)
       << " seconds\n";
  return 0;
}

Enter n: 30
fib(30) = 832040
Elapsed time = 2 seconds

    Поставяме трасиращи печати във функцията, за да видим колко пъти се извиква функцията.
// fibtrace.cpp
#include <iostream>
using namespace std;

long fib(int n)
{ cout << "Entering fib: n = " << n << "\n";
  long f;
  if (n <= 2) f = 1;
  else f = fib(n - 1) + fib(n - 2);
  cout << "Exiting fib: n = " << n
       << " return value = " << f << "\n";
  return f;
}

int main()
{ cout << "Enter n: ";
  int n;
  cin >> n;
  long f = fib(n);
  cout << "fib(" << n << ") = " << f << "\n";
  return 0;
}

Enter n: 5
Entering fib: n = 5
Entering fib: n = 4
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Exiting fib: n = 4 return value = 3
Entering fib: n = 3
Entering fib: n = 2
Exiting fib: n = 2 return value = 1
Entering fib: n = 1
Exiting fib: n = 1 return value = 1
Exiting fib: n = 3 return value = 2
Exiting fib: n = 5 return value = 5
fib(5) = 5

    Този алгоритъмът за пресмятане на  n-тото число на Фибоначи е неефективен, защото фунцията се извиква многократно с една и съща стойност на входния си параметър. За конкретния пример за да се пресметне fib(5)- fib(1) се вика 2 пъти, fib(2) - 3 пъти, fib(3) - 2 пъти и fib(4) - веднъж. Сложността на този алгоритъм е O(qn), където q > 1.
    Не е трудно да се реализира итеративен алгоритъм за решаване на същата задача.
// fibloop.cpp
#include <iostream>
using namespace std;
#include "ccc_time.cpp"

long fib(int n)
{ if (n <= 2) return 1;
  long fold = 1;
  long fold2 = 1;
  long fnew;
  for (int i = 3; i <= n; i++)
  { fnew = fold + fold2;
    fold2 = fold;
    fold = fnew;
  }
  return fnew;
}

int main()
{ cout << "Enter n: ";
  int n;
  cin >> n;
  Time before;
  long f = fib(n);
  Time after;
  cout << "fib(" << n << ") = " << f << "\n";
  cout << "Elapsed time = " << after.seconds_from(before) << " seconds\n";
  return 0;
}

Enter n: 45
fib(45) = 1134903170
Elapsed time = 0 seconds

    В таблицата са дадени времената за работа на двата алгоритъма.
 

n fib(n) rec sec loop sec
30 832040 2 < 1
32 2178309 3 < 1
34 5702887 8 < 1
36 14930352 22 < 1
45 1134903170 - < 1

 Нерекурсивният вариант за пресмятане на  n-тото число на Фибоначи е по-ефективен.

* За пресмятане на  n! и двата варианта - рекурсивния и итерационния - са еднакво ефективни.
* Двоичното търсене може да се направи нерекурсивно - двата варианта са приблизително еднакво ефективни..
* Сортиране чрез сливане е трудно да се направи нерекурсивно.
* Бързата сортировка може да си направи нерекурсивна.