Общее определение
Рекурсия – процесс повторения элемента самоподобным образом. Т.е. в описании элемента содержится сам элемент.
Например, рассмотрим операцию факториал, которая определяется в математике следующим образом (в высшей математике - факториал это интеграл от Гамма-функции):
Как видно, определение факториала с точки зрения математики включает само себя.
Условие равенства факториала нуля единице называется базой рекурсии. Остальная часть определения, включающая определение через саму функцию – шаг рекурсии.
Для того, что бы лучше понять, что такое рекурсия рассмотрим простую задачу: Представим, что человеку нужно пройти 1000 шагов. Для того, что бы пройти 1000 шагов, человеку надо сделать 1 шаг и ещё 999. Для того, что бы пройти 999 шагов, надо сделать 1 шаг и ещё 998 и т.д., пока не дойдем до того, что нужно сделать 1 шаг. Таким образом, задача прохождения 1000 шагов, в общем случае, за один раз невыполнимая, разбивается на 1000 задач до того момента, пока не становится невыполнима, а затем сворачивается назад.
Важно понимать, что если база рекурсии задана неправильно, то и сама рекурсия выполнена не будет, что приведет к ошибке, связанной с заполнением всей, доступной для работы, памяти.
Рекурсивное вычисление факториал
Рассмотрим приведенный выше пример определения факториала. Опишем его двумя различными способами. В листинге 6.1. приведен пример реализации факториала через рекурсию, а в листинге 6.2 обычным итерационным методом.
Листинг 6.1. Рекурсивный факториал
- Код: выделить все
long int factorialRec(int n) {
if (n==0)
return 0;
else
return n*factorialRec(n-1);
}
Листинг 6.2. Итерационный факториал
- Код: выделить все
long int factorialRec(int n) {
int factorialIter =1;
while (n>1) {
factorialIteer*=n;
n--;
}
}
В данном примере, база рекурсии описана после if, а после else описан шаг рекурсии.
Можно показать, что любую рекурсивную функцию можно заменить на нерекурсивную или итерационную.
Наибольший общий делитель
Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей.
Пример: для чисел 70 и 105 наибольший общий делитель равен 35.
Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не ноль.
НОД обладает следующим свойством:
- Код: выделить все
НОД(a,b)=НОД(a-b,b),a≥b
Это свойство несложно доказать. Если d – делитель чисел a и b, то на d делится и разность чисел a и b. Обратно, если d является делителем чисел a-b и b, то и их сумма (a-b)+b=a делится на d. Таким образом, всякий общий делитель чисел a и b является общим делителем чисел a-b и b, и наоборот. Поэтому и наибольшие делители у этих пар чисел совпадают.
Так же, исходя из смысла операции, выполняются следующие соотношения:
- Код: выделить все
НОД(1,n)= 1; НОД(m,1)= 1;
НОД(0,n)= n; НОД(m,0)= m;
НОД(m,m) = m;
Данный алгоритм можно оптимизировать(см. http://sotvorimvmeste.ru/viewtopic.php?f=60&t=159)
Наименьшее общее кратное
Наряду с наибольшим общим делителем определена и функция вычисления наименьшего общего кратного. Наиме́ньшее о́бщее кра́тное (НОК) двух целых чисел m и n есть наименьшее натуральное число, которое делится на m и n без остатка.
НОК связан с НОД следующим соотношением:
- Код: выделить все
НОК(a,b)*НОД(a,b)=a*b
Взаимно простые числа
Целые числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме ±1.
Число звеньев в цепной передаче делают таковыми, что бы на двух цепях они были взаимно простыми. Таким образом, каждый сегмент изнашивается равномерно.
Числа являются взаимно простыми если их НОД равен 1.