Int main()

{ int a, n = 4, m = 3;

a = AkkR(m, n);

cout<<a;

}

Int AkkR(int m, int n)

{ if(m < 0 || n < 0) return - 1;

if(m == 0)

return n + 1;

else

if(m > 0 && n == 0)

return AkkR(m-1, 1);

else

return AkkR(m-1, AkkR(m, n-1));

}

Уже при n = 4 и m = 3 функция Аккермана вызвала сама себя 10307 раз (результат - число125).

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

Особенности функции Аккермана (глубокая рекурсиия и быстрый рост значений) используют для тестирования компиляторов и сравнения скорости различных языков программирования.

Можно сформулировать следующие правила разработки рекурсивного алгоритма:

 

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

- обобщенные начальные условия шага – это формальные параметры функции;

- начальные условия следующего шага – это фактические параметры рекурсивного вызова;

- рекурсивная функция должна проверять условиие завершения рекурсии;

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

Таким образом:

- формальные параметры рекурсивной функции представляют начальное состояние для тек. шага процесса; 

-фактич. параметры рекурс. вызова представляют нач. состояние для следующего шага, в кот. производится переход из тек. при рекурсивном вызове;

 -автоматические переменные представляют внутренние характеристики процесса на тек. шаге его выполнения;

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

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

Во многих случаях рекурсивные функции можно заме-нить на эквивалентные нерекурсивные функции.

  Нерекурсивная программа  для вычисления функции Аккермана:   

Int main()

{ typedef struct st { int i, j, k, z, lr;

struct st *pst;

} ST;

ST *u, *dl = NULL; int l, x, y, n;

Int smacc(int, int);

int an, ax, ay, rz, t;

scanf("%i %i %i", &n, &x, &y);

an = n; ax = x; ay = y; l = 1; /* - замена вызова - */

goto ackr; /* t=ackr(n,x,y); */

l1: t = rz; printf("\n %d ", t);

goto jackr; /*начало фрагмента заменяющего функцию ackr */

ackr: u=( ST *) malloc( sizeof (ST) );

u -> i = an; u -> j = ax;

u -> k = ay; u -> lr = l;

u -> pst = dl; dl = u;

if (an == 0 || ay == 0)

dl -> z = smacc(an, ax);

else

{ an=dl->i; ax=dl->j;

ay=dl->k-1; l=2; goto ackr;

l2: dl->z=rz; an=dl->i-1; ax=rz;

ay=dl->j; l=3; goto ackr;

l3: dl->z=rz;

}

rz=dl->z; an=dl->i; ax=dl->j;

ay=dl->k; l=dl->lr;

u=dl; dl=u->pst;

free(u);

switch(l)

{ case 1: goto l1;

case 2: goto l2;

case 3: goto l3;

}

jackr: return 0;

}

int smacc( int n,int x ) /* вспомогательная функция */

{ switch (n)

{ case 0: return(x+1);

case 1: return (x);

case 2: return (0);

case 3: return (1);

default: return (2);

}

}

Недостатки рекурсивных функций:

• требуется большой объем памяти для многократного размещения в памяти формальных параметров и локальных переменных рекурсивной функции;

• большой расход времени на многократное выполнение команд вызова функции

Пример. Линейный кроссворд

Для заданного набора слов построить линейный кроссворд. Если окончание одного слова совпадает с началом следующего более чем в одной букве (напр., МАТРАС-РАСИСТ), то такие слова можно объединить в цепочку.

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

- рекурс. функция выполняет попытку присоединения очередного слова к уже выстроенной цепочке;

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

- условием завершения рекурсии явл. отсутствие еще не присоединенных к цепочке слов (успешное завершение), либо невозможность завершения цепочки ни через одно из оставшихся слов (неудача).

Множество возможных вариантов строится на основе обычного комбинаторного перебора всех допустимых сочетаний (последов.стей) из элементов множества (в данном случае - слов). Это множество явл. глобальной структурой данных, из кот. на каждом шаге извлекается очередной элемент, но по завершении просмотра варианта (после рекурс. вызова) возвращается обратно.

 Для представления множества слов б. исп.  массив указателей на строки. Исключение строки из множества б. заключаться в установке указателя на строку нулевой длины. Теперь можно “набросать” общий вид рекурс. функции 

Пример. Пусть дана цепочка слов:

"РАСИСТ", "МАТРАС", "МАСТЕР", "СИСТЕМА", "СТЕРВА", NULL

#include <iostream>

using namespace std;

char *w[] = {"РАСИСТ", "МАТРАС", "МАСТЕР", "СИСТЕМА", NULL};

//Функция проверки совпадения окончания первого слова с началом второго: