4. Рекурсия и итерация

** Най-голям общ делител [1.2.3]
* Алгоритъм на Евклид за намиране на най-голям общ делител
// gcd.c
#include <stdio.h>

unsigned gcd1(unsigned a, unsigned b)
{ unsigned swap;
while (b > 0) { swap = b; b = a%b; a = swap; }
return a;
}

unsigned gcd2(unsigned a, unsigned b)
{ return (0 == b) ? a : gcd2(b, a%b); }

int main(void)
{ const unsigned a = 1, b = 125;
printf("%u \n", gcd1(a, b));
printf("%u \n", gcd2(a, b));
return 0;
}
* Да се напише метода само с изваждане.
* Да се напише функция за съкращаване на прости дроби.

Задача 4а. Да се напише програма за намиране на НОД на n естествени числа.

** Връщане от рекурсия и използване на променливите [1.2.5]
* Рекурсивно отпечатване на цифрите на число
// digit2.c
#include <stdio.h>

void printN(unsigned n)
{ if (n >= 10) printN(n/10);
printf("%u ", n%10);
}
int main(void)
{ unsigned m = 1234;
printN(m);
return 0;
}

* Пресмятане на n! и изследване на ефективността на реализациите [1.2.5]

/* Два варианта за пресмятане на n! [1.2.5] */
// fact.c
#include <stdio.h>

unsigned long fact1(unsigned i)
{ if (1 == i) return 1;
return i * fact1(i - 1);
}

unsigned i;
unsigned long fact2()
{ if (1 == i) return 1;
return i-- * fact2(); // --i*fact();
}

const unsigned n = 6;
int main(void)
{ printf("fact1: %u! = %lu \n", n, fact1(n)); i=n; // i=n+1;
printf("fact2: %u! = %lu \n", n, fact2());
return 0;
}

** Рекурсия и използване на глобални променливи [1.2.5]
* За дадено естествено число n (n < 9) да се отпечатат в нарастващ и намаляващ ред числата 10^k (0 < k < n).
// print0.c
#include <stdio.h>
const unsigned n = 6;

void printRed1(unsigned k, unsigned long res)
{ printf("%lu ", res);
if (k < n) printRed1(k + 1, res*10);
printf("%lu ", res);
}

unsigned k = 0;
void printRed2(unsigned long res)
{ k++;
printf("%lu ", res);
if (k < n) printRed2(res*10);
printf("%lu ", res);
}

unsigned long res = 1;
void printRed3()
{ k++;
res *= 10;
printf("%lu ", res);
if (k < n) printRed3();
printf("%lu ", res);
res /= 10;
}
int main(void)
{
printRed1(1,10);
printf("\n");
printRed2(10);
printf("\n");
k = 0;
printRed3();
printf("\n");
return 0;
}

Задача 4b: За дадено естествено число n (n < 10⁹) да се отпечатат в нарастващ и намаляващ ред числата 10^k (0 < k < n).

Задача 4c: За естественото число a дефинираме редицата

a₀= a,
a_k+₁ = a_k/2, ако a_k е четно или
a_k+₁ = 3a_k + 1, ако a_k е нечетно.

Ако някой член от редицата a_k = 1, то тази стойност се счита за край на редицата. Хипотезата е, че всяко естествено число a генерира крайна редица.