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

#include <iostream>
using namespace std;

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

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

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

// calculate пресмята стойността на
// израза, записан в s
// и премества s след израза, който
// е пресметнала

// <израз> ::= <цифра> | (<израз><оп><израз>)
// <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
// <оп>    ::= + | - | * | /
int calculate(char const*& s)
{
	if (*s >= '0' && *s <= '9')
		return *s++ - '0';
	// (<израз><оп><израз>)
	int le = calculate(++s);
	char op = *s;
	int re = calculate(++s);
	s++;
	switch (op)
	{
		case '+':return le + re;
		case '-':return le - re;
		case '*':return le * re;
		case '/':return le / re;
		default:return 0;
	}
}

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

int sum(int a[], int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return a[0];
	// return a[n-1] + sum(a, n-1);
	// return a[0] + sum(a + 1, n-1);
	return a[0] + a[n-1] + sum(a + 1, n-2);
}
/*
bool member(int x, int a[], int n)
{
	if (n == 0)
		return false;
	bool r = member(x, a, n-1);
	if (r)
		return true;
	if (x == a[n-1])
		return true;
	return false;
}
*/

bool member(int x, int a[], int n)
{
	return n != 0 && (x == a[n-1] ||
			           member(x, a, n-1));
}

bool ordered(int a[], int n)
{
	return n <= 1 || a[0] <= a[1] &&
			         ordered(a + 1, n - 1);
}

/*
bool different(int a[], int n)
{
	if (n == 0)
		return true;
	if (member(a[0], a + 1, n - 1))
		return false;
	// n != 0 && a[0] не се повтаря
	if (!different(a + 1, n - 1))
		return false;
	return true;
}*/

/*
bool different(int a[], int n)
{
	if (n == 0)
		return true;
	if (member(a[0], a + 1, n - 1))
		return false;
	// n != 0 && a[0] не се повтаря
	return different(a + 1, n - 1);
}*/

bool different(int a[], int n)
{
	return n == 0 || !member(a[0], a + 1, n - 1)
			      && different (a + 1, n - 1);
}


/*
 * if (!U) return false;
 * return true;
 *
 * ^
 * |
 * v
 *
 * return U;
 */

/*
 * if (U) return true;
 * return false;
 *
 * ^
 * |
 * v
 *
 * return U ? true : false;
 *
 * ^
 * |
 * v
 *
 * return U;
 *
 *
 *
 *if (V) return false;
 *return U;
 *
 * ^
 * |
 * v
 * !V && U
 */

int main()
{
	cout << fact(5) << endl;
	// !!! cout << fact(-1) << endl;
	cout << gcd(120, 84) << endl;
	// !!! cout << gcd(10, 0) << endl;
	cout << pow(1.0001, 1000000) << endl;
	char str[] = "(((2+3)-(4*5))/2)";
	char const* s = str;
	cout << calculate(s) << endl;
	cout << fibonacci(10) << endl;
	int a[] = {1, 2, 3, 4, 5, 6 };
	cout << sum(a, 5) << endl;
	cout << member(3, a, 6) << endl;
	cout << member(7, a, 6) << endl;
	cout << ordered(a, 6) << endl;
	cout << different(a, 6) << endl;
}