Рекурсивные функции
Рассмотрим принципиальные возможности, которые предоставляет язык Си++ для организации рекурсивных алгоритмов. Предварительно отметим, что различают прямую и косвенную рекурсии. Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна. Если в теле функции явно используется вызов этой функции, то имеет место прямая рекурсия, т.е. функция, по определению, рекурсивная. Классический пример - функция для вычисления факториала неотрицательного целого числа.
double fact(double 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();
}
Дата добавления: 2020-12-11; просмотров: 394;