/*
 * 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 main() {
	cout << fact(4) << endl;
	cout << power(2, -5) << endl;
	cout << gcd(12, 20) << endl;
	cout << fibonacci(45) << endl;
	cout << fibonacci_cycle(45) << endl;
	cout << "Alive!" << endl;
	return 0;
}