Рекурсията

Непряка рекурсия.
    Ако една функция f1 вика друга функция f2, а втората функция f2 вика първата f1, казваме, че има непряка рекурсия.
     Пример. Хилбертови криви.
    Хилбертова крива от 1-ви ред H₁ се получава като се чертае наляво - надолу - надясно единичната отсечка. H₂ се състои от 4 криви H₁ намалени наполовина, първата завъряна на +90, втората отместена на 1/2 наляво,  третата отместена на 1/2 надясно и четвъртата завъртяна на -90 градуса и отместена 1/2 надясно. По същия начин е получена и кривата от 3-ти ред H₃ от H₂. Процесът може да продължи с получаване на H₄, H₅ и т. н. Има 4 елемента A, B, C и D, от които се състои всяка крива. За да напишем рекурсията, нека предположим, че можем да чертаем тези елементи и отсечки като "костенурка-графика":
- left - наляво;
- down - надолу;
- right - надясно;
- up - нагоре
с дължини 1/n за кривата H_n.

Получаваме следната схема на рекурсията:
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;
} 
 

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

f₁ =  f₂ = 1 и  f_i =  f_{i - 1} +  f_{i - 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;
}

    Поставяме трасиращи печати във функцията, за да видим колко пъти се извиква функцията.
// 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;
}