/*
 * recursion.cpp
 *
 *  Created on: 17.12.2013
 *      Author: trifon
 */

#include <iostream>
using namespace std;

int fact(int n) {
	if (n == 0)
		return 1;
	int result = n * fact(n-1);
	return result;
}

double power(double x, int n) {
	if (n == 0)
		return 1;
	if (n < 0)
		return 1 / power(x, -n);
	return x * power(x, n-1);
}

int gcd(int a, int b) {
	if (a == b || a == 0 || b == 0)
		return a;
	if (a > b)
		return gcd(a - b, b);
	return gcd(a, b - a);
}

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

int memo[100] = { 0 };

int fibonacci_faster(int n) {
	if (n <= 1)
		return n;
	if (memo[n] != 0)
		return memo[n];

	memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
	return memo[n];
}


int fibonacci_cycle(int n) {
	if (n <= 1)
			return n;
	int pred = 0, last = 1;
	for(int i = 2; i <= n; i++) {
		int next = pred + last;
		pred = last;
		last = next;
	}
	return last;
}

// сума на цифрите на дадено число
int sumdigits_iter(int n) {
	int sum = 0;
	while (n > 0) {
		sum += n % 10;
		n /= 10;
	}
	// n == 0
	return sum;
}

int sumdigits_rec(int n) {
	if (n == 0)
		return 0;
	return sumdigits_rec(n / 10) + n % 10;
}

// разлагане на число на прости делители
void prime_divisors(int n) {
	if (n == 1)
		return;
	// търсим най-малкия делител на n, който е >1
	int d = 2;
	while (n % d != 0)
		d++;
	// n % d == 0
	// в момента d е най-малкият прост делител на n
	cout << d << ".";
	prime_divisors(n / d);
}

// разлагане на число на прости делители
void prime_divisors_iter(int n) {
	while (n != 1) {
		// търсим най-малкия делител на n, който е >1
		int d = 2;
		while (n % d != 0)
			d++;
		// n % d == 0
		// в момента d е най-малкият прост делител на n
		cout << d << ".";
		n /= d;
	}
}

/**
 * <израз> ::= <цифра> | (<израз><операция><израз>)
 */
// промяна: искаме след пресмятането на израза
// exp да сочи след края му
int calculate_expression(char const*& exp) {
	if (*exp >= '0' && *exp <= '9') {
		return *(exp++) - '0';
	}

	// прескачаме (
	int l = calculate_expression(++exp);
	// къде сочи exp в момента?
	// към операцията!
	char op = *exp;
	// прескачаме операцията
	int r = calculate_expression(++exp);
	// къде сочи exp в момента?
	// към )
	// трябва да прескочим и нея!
	exp++;
	switch(op) {
	case '+': return l + r;
	case '-': return l - r;
	case '*': return l * r;
	case '/': return l / r;
	}
}

// сума на елементите на масив
int sum_array(int a[], int n) {
	if (n == 0)
		return 0;
	return a[0] + sum_array(a + 1, n - 1);
}

// проверка за съществуване
/*
 *
 bool find_array(int a[], int n, int x) {
	if (n == 0)
		return false;
	if (a[0] == x)
		return true;
	return find_array(a + 1, n - 1, x);
}

bool find_array(int a[], int n, int x) {
	if (n == 0)
		return false;
	return a[0] == x || find_array(a + 1, n - 1, x);
}
*/
bool find_array(int a[], int n, int x) {
	return n > 0 && (a[0] == x || find_array(a + 1, n - 1, x));
}

// проверка дали един масив сортиран
bool is_sorted(int a[], int n) {
	if (n <= 1)
		return true;
	return a[0] <= a[1] && is_sorted(a + 1, n - 1);
}

// проверка дали масив се състои от различни елементи
bool different_elements(int a[], int n) {
	if (n == 0)
		return true;
	return !find_array(a + 1, n - 1, a[0])
		&& different_elements(a + 1, n - 1);
}

int main() {
	cout << fact(4) << endl;
	cout << power(2, -5) << endl;
	cout << gcd(12, 20) << endl;
	cout << fibonacci_faster(4) << endl;
	cout << fibonacci_cycle(4) << endl;
	cout << sumdigits_iter(214352) << endl;
	cout << sumdigits_rec(214352) << endl;
	prime_divisors(214352);
	cout << endl;
	prime_divisors_iter(214352);
	cout << endl;

	const int MAX = 100;
	char exp[MAX];
	cout << "Въведете израз: ";
	cin.getline(exp,MAX);
	char const* p = exp;
	cout << calculate_expression(p) << endl;

	int a[] = {5,13,4,1,10,2,10,5,5}; //{ 3, 5, 2, 1, 6, 4, 9 };
	cout << sum_array(a, 7) << endl;
	cout << find_array(a, 7, 7) << endl;
	cout << find_array(a, 7, 6) << endl;

	cout << is_sorted(a, 7) << endl;
	cout << is_sorted(a, 2) << endl;

	cout << different_elements(a, 7) << endl;

	cout << "Alive!" << endl;
	return 0;
}