Функции и процедуры. Рекурсия

Всех вас в свое время на уроках математики учили находить наибольший общий делитель двух чисел. Для этого нужно было первым делом разложить их на простые множители. Сейчас мы рассмотрим другой алгоритм, который и реализовывать проще, да и работает он быстрее. Он основан на следующем свойстве НОД:

 

НОД(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, и наоборот. Поэтому и наибольшие делители у этих пар чисел совпадают.

Пользуясь этой формулой, можно легко написать рекурсивную функцию для вычисления НОД. Надо лишь не забывать про терминальное условие.

 

function NOD (a,b : integer) : integer;

begin

  if a<b then swap(a,b);      {переставляем большее число

на первое место} 

  if  b=0 then NOD:=a         {терминальное условие: НОД(a,0)=a}

  else NOD:=NOD(a-b,b);

end;

 

Работу алгоритам можно еще ускорить, если воспользоваться формулой

 

НОД(a,b)=НОД(a mod b,b).

 

Алгоритм вычисления НОД по этой формуле называют алгоритмом Евклида.

Заметим, что эта формула верна для всех a и b, но если a<b, то a mod b = a и формула вырождается в тривиальную. Чтобы обойтись без процедуры swap, можно пользоваться формулой НОД(a,b)=НОД(b, a mod b).

function NOD (a,b : integer) : integer;

begin

  if  b=0 then NOD:=a         {терминальное условие: НОД(a,0)=a}

  else NOD:=NOD(b, a mod b);

end;