Рекурентна формула за НОД

[bystro]

Здравейте,

Започнах да чета една книга по алгоритми. Стигнах до част със фактуриел и рекурентни функции.

Едната задача беше да се предложи рекурентна формула за повдигане на x в степен y (x[tex]\epsilon[/tex]R, y[tex]\epsilon[/tex]N).
Тази я реших по следния начин:

[tex]p(x^{y})=\begin{cases} x,y = 1 \\ p(x^{y-1}), y > 1\end{cases}[/tex]

Но задачата за рекурентна формула за намиране на най-големия общ делител на две естествени числа. Не мога да схвана как точно да напиша делението.

Бих се радвал и на обяснение, ако имате предложения.

[Добромир Глухаров]

Задачата за степенуване може да се реши със следната рекурентна зависимост:

$x^n=p(x,n)=\begin{cases}1,&n=0\\x.p(x,n-1),&n>0\end{cases}$

Или с по-бързата за изпълнение (с по-малко стъпки):

$x^n=p(x,n)=\begin{cases}1,&n=0\\\left(p\left(x,\frac{n}{2}\right)\right)^2,&n-четно\\x.p(x,n-1),&n-нечетно\end{cases}$

където дали $n$ е четно или нечетно може да се провери например при програмиране на $C,C++,JavaScript$ чрез оценяване на Булевия израз $n\%2 == 0$ - ако е истина - четно, ако е лъжа - нечетно, или дори на по-краткия израз $n\%2$ -ако е лъжа - четно, ако е истина - нечетно.

А за най-голям общ делител може да се опита формулата (рекурентната зависимост):

$gcd(a,b)=\begin{cases}a,&b==0\\gcd(b,a\%b),&b>0\end{cases}$

Тук $a\%b$ е остатъкът при делене $a$ на $b$ - например $7\%4=3;\ 7\%3=1;\ 11\%7=4$