Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Рекурсивные функцииРассмотрим принципиальные возможности, которые предоставляет язык Си++ для организации рекурсивных алгоритмов. Предварительно отметим, что различают прямую и косвенную рекурсии. Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна. Если в теле функции явно используется вызов этой функции, то имеет место прямая рекурсия, т.е. функция, по определению, рекурсивная. Классический пример - функция для вычисления факториала неотрицательного целого числа. 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(); }
|