Рекурсия(Явная и неявная)

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

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

Реализация рекурсии:

Вызов рекурсивной функции должен выполняться по условию

Последовательный вызов функцией самой себя называют рекурсивным спуском, последовательный выход из многократного вызова — рекурсивным подъёмом.

При каждом рекурсивном вызове функции заново выделяется память под локальные переменные.

Примеры рекурсии:

Рекурсивная функция вычисления факториала (прямая рекурсия)

long Fact(int k)

{ if (k==0) return 1;

return (k*Fact(k-1)); // рекурсивный вызов!

}

1)Прямая рекурсия функции main() на языке C++:

#include < iostream>

using namespace std;

int main()

{

cout < < " Hello world! " < < endl;

main();

return 0;

}

2)Косвенная рекурсия функции main() на языке C++:

#include < iostream>

using namespace std;

void f();

int main()

{

cout < < " Hello world! " < < endl;

f();

return 0;

}

void f()

{

main();

}

В обоих примерах на экране монитора достаточно долго будет выводится радостный текст

Hello world!

а затем произойдёт аварийное завершение программы из-за переполнения стека.

Сортировка Хоара (Итеративный вариант)

#define MAXSTACK 2048 // максимальный размер стека

template< class T>

void qSortI(T a[], long size) {

long i, j; // указатели, участвующие в разделении

long lb, ub; // границы сортируемого в цикле фрагмента

long lbstack[MAXSTACK], ubstack[MAXSTACK]; // стек запросов

// каждый запрос задается парой значений,

// а именно: левой(lbstack) и правой(ubstack)

// границами промежутка

long stackpos = 1; // текущая позиция стека

long ppos; // середина массива

T pivot; // опорный элемент

T temp;

lbstack[1] = 0;

ubstack[1] = size-1;

do {

// Взять границы lb и ub текущего массива из стека.

lb = lbstack[ stackpos ];

ub = ubstack[ stackpos ];

stackpos--;

do {

// Шаг 1. Разделение по элементу pivot

ppos = (lb + ub) > > 1;

i = lb; j = ub; pivot = a[ppos];

do {

while (a[i] < pivot) i++;

while (pivot < a[j]) j--;

if (i < = j) {

temp = a[i]; a[i] = a[j]; a[j] = temp;

i++; j--;

}

} while (i < = j);

// Сейчас указатель i указывает на начало правого подмассива,

// j - на конец левого (см. иллюстрацию выше), lb? j? i? ub.

// Возможен случай, когда указатель i или j выходит за границу массива

// Шаги 2, 3. Отправляем большую часть в стек и двигаем lb, ub

if (i < ppos) { // правая часть больше

if (i < ub) { // если в ней больше 1 элемента - нужно

stackpos++; // сортировать, запрос в стек

lbstack[ stackpos ] = i;

ubstack[ stackpos ] = ub;

}

ub = j; // следующая итерация разделения

// будет работать с левой частью

} else { // левая часть больше

if (j > lb) {

stackpos++;

lbstack[ stackpos ] = lb;

ubstack[ stackpos ] = j;

}

lb = i;

}

} while (lb < ub); // пока в меньшей части более 1 элемента

} while (stackpos! = 0); // пока есть запросы в стеке

}

Сортировка Хоара (рекурсивный вариант)

template< class T>

void quickSortR(T* a, long N) {

// На входе - массив a[], a[N] - его последний элемент.

long i = 0, j = N; // поставить указатели на исходные места

T temp, p;

p = a[ N> > 1 ]; // центральный элемент

// процедура разделения

do {

while (a[i] < p) i++;

while (a[j] > p) j--;

if (i < = j) {

temp = a[i]; a[i] = a[j]; a[j] = temp;

i++; j--;

}

} while (i< =j);

// рекурсивные вызовы, если есть, что сортировать

if (j > 0) quickSortR(a, j);

if (N > i) quickSortR(a+i, N-i);

}

Ханойские башни:

Даны три стержня, на один из которых нанизаны восемь колец, причем кольца отличаются размером и лежат меньшее на большем. Задача состоит в том, чтобы перенести пирамиду из восьми колец за наименьшее число ходов. За один раз разрешается переносить только одно кольцо, причём нельзя класть большее кольцо на меньшее.

#include < stdio.h>

#include < conio.h>

char a, b, c;

int num;

void hanoy(int num, char a, char b, char c){

if(num> 0)

{

hanoy(num-1, a, c, b);

printf(" %c---> %c\n", a, c);

hanoy(num-1, b, a, c);

}

}

void main(){

printf(" number of rings=");

scanf(" %d", & num);

a='A'; b='B'; c='C';

hanoy(num, a, b, c);

}