Рекурсивные функции

Рассмотрим принципиальные возможности, которые предоставляет язык Си++ для организации рекурсивных алгоритмов. Предварительно отметим, что различают прямую и косвенную рекурсии. Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна. Если в теле функции явно используется вызов этой функции, то имеет место прямая рекурсия, т.е. функция, по определению, рекурсивная. Классический пример - функция для вычисления факториала неотрицательного целого числа.

long fact(int k){

if (k < 0) return 0;

if (k == 0) return 1;

return k * fact(k-l);

}

Для отрицательного аргумента результат по определению факториала не существует. В этом случае функция возвратит нулевое значение. Для нулевого параметра функция возвращает значение 1, так как по определению, 0! равен 1. В противном случае вызывается та же функция с уменьшенным на 1 значением параметра и результат умножается на текущее значение параметра. Тем самым для положительного значения параметра k организуется вычисление произведения

k * (k-l) * (k-2) *...*3*2*1*1

Обратите внимание, что последовательность рекурсивных обращений к функции fact прерывается только при вызове fact(0). Именно этот вызов приводит к последнему значению 1 в произведении, так как последнее выражение, из которого вызывается функция, имеет вид:

1 * fact(1-1)

Поскольку в теле самой функции fact() присутствует её вызов, то по определению такую функцию называют прямой рекурсивной функцией.

В качестве еще одного примера рекурсии рассмотрим функцию QuickSort(), реализующую алгоритм быстрой сортировки.

//Программа 6.4

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>

#define DIMENSION 100

void QuickSort(int array[], int First, int Last)

{

int Temp, LowerBoundary, UpperBoundary, Separator;

LowerBoundary = First;

UpperBoundary = Last;

Separator = array[(First + Last) / 2];

do{

while (array[LowerBoundary] < Separator) LowerBoundary++;

while (array[UpperBoundary] > Separator) UpperBoundary--;

if (LowerBoundary <= UpperBoundary){

Temp = array[LowerBoundary];

array[LowerBoundary++] = array[UpperBoundary];

array[UpperBoundary--] = Temp;

}

} while (LowerBoundary <= UpperBoundary);

if (First<UpperBoundary)QuickSort(array,First,UpperBoundary);

if (LowerBoundary<Last) QuickSort(array, LowerBoundary, Last);

}

void main()

{

int array[DIMENSION], i = 0;

for (; i < DIMENSION; array[i++] = rand()%1000);

QuickSort(array, 0, DIMENSION -1);

printf("\n\n");

for (i = 0; i < DIMENSION; printf("\n%d", array[i++]));

getchar();

}