Необходимый материал

Необходимый материал

Сообщение EgorovAD MEPhI » 09 дек 2013, 08:43

Рекурсия
Общее определение
Рекурсия – процесс повторения элемента самоподобным образом. Т.е. в описании элемента содержится сам элемент.
Например, рассмотрим операцию факториал, которая определяется в математике следующим образом (в высшей математике - факториал это интеграл от Гамма-функции):
Изображение
Как видно, определение факториала с точки зрения математики включает само себя.
Условие равенства факториала нуля единице называется базой рекурсии. Остальная часть определения, включающая определение через саму функцию – шаг рекурсии.

Для того, что бы лучше понять, что такое рекурсия рассмотрим простую задачу: Представим, что человеку нужно пройти 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.
EgorovAD MEPhI
Администратор
 
Сообщений: 155
Зарегистрирован: 04 ноя 2011, 11:49

Вернуться в Тема 8. Рекурсия

Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron