#include <stdio.h>

int power_recursive(int x, int n)
{
    //printf("power_recursive\n");
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    else
        return x * power_recursive(x, n - 1);
}

int power_recursive_opt(int x, int n)
{
    //printf("power_rec_opt\n");
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    int pow = power_recursive_opt(x, n / 2);
    if (n % 2 == 0)
        return pow * pow;
    else
        return x * pow * pow;
}

int power_iterative(int x, int n)
{
    int pow = 1;
    for (int i = 1; i <= n; i++)
        pow *= x;
    return pow;
}

int fact_recursive(int n)
{
    if (n == 0)
        return 1;
    else
        return n * fact_recursive(n - 1);
}

int fact_iterative(int n)
{
    int fact = 1;
    for (int i = 1; i <= n; i++)
        fact *= i;
    return fact;
}

int fibo_recursive(int n)
{
    if (n <= 2)
        return 1;
    else
        return fibo_recursive(n - 2) + fibo_recursive(n - 1);
}

int fibo_iterative(int n)
{
    int prev = 1, current = 1;

    if (n <= 2)
        return 1;

    for (int i = 2; i < n; i++)
    {
        int temp = current;
        current += prev;
        prev = temp;
    }
    return current;
}

int max_recursive(int a[], int n)
{
    if (n == 0)
        return a[0];
    int max = max_recursive(a, n - 1);
    return (max > a[n - 1]) ? max : a[n - 1];
}

void print_recursive(int a[], int n)
{
    if (n != 0)
    {
        print_recursive(a, n - 1);
        printf("a[%d]=%d, ", n - 1, a[n - 1]);
    }
    else
        return;
}
int sum_of_digits_recursive(int n)
{
    if (n == 0)
        return 0;
    else
        return n % 10 + sum_of_digits_recursive(n / 10);
}

int reverse_number_recursive(int n, int rev)
{
    if (n == 0)
        return rev;
    return reverse_number_recursive(n / 10, rev * 10 + n % 10);
}

int GCD_recursive(int a, int b)
{
    if (b == 0)
        return a;
    return GCD_recursive(b, a % b);
}
int main()
{
    int x = 2, n = 15;
    int a[] = {2, 8, 6, 14, -8, 7, 41, 11, 6};
    int large_num = 845621;

    printf("%d^%d izracunato rekurzivno (n poziva f-je) je %d\n", x, n, power_recursive(x, n));
    printf("%d^%d izracunato iterativno je %d\n", x, n, power_iterative(x, n));
    printf("%d^%d izracunato rekurzivno (log n poziva f-je) je %d\n", x, n, power_recursive_opt(x, n));

    printf("Faktorijel broja %d izracunat rekurzivno je %d\n", n, fact_recursive(n));
    printf("Faktorijel broja %d izracunat iterativno je %d\n", n, fact_iterative(n));

    printf("%d. broj Fibonacijevog niza izracunat rekurzivno je %d\n", n, fibo_recursive(n));
    printf("%d. broj Fibonacijevog niza izracunat iterativno je %d\n", n, fibo_iterative(n));

    printf("Maksimalni element niza izracunat rekurzivno je %d\n", max_recursive(a, sizeof(a) / sizeof(a[0])));

    printf("Elementi niza stampani rekurzivnom funkcijom: \n");
    print_recursive(a, sizeof(a) / sizeof(a[0]));
    printf("\n");

    printf("Suma cifara broja %d je %d\n", large_num, sum_of_digits_recursive(large_num));
    printf("Obrnuti broj od broja %d je %d\n", large_num, reverse_number_recursive(large_num, 0));

    int b = 60, c = 14;
    printf("Najveci zajednicki delilac brojeva %d i %d je %d\n", b, c, GCD_recursive(b, c));
}