#include <iostream>
using namespace std;


/**
 * Итеративен метод: най-бърз, препоръчва се.
 */
bool contains(const int *a, int n, int x) {
	for(int i = 0; i < n; ++i) {
		if(a[i] == x) {
			return true;
		}
	}
	
	return false;
}

/*
 * Псевдо-рекурсивен: отново се позлва идексиране.
 * Има недостатъците и на двата подхода.
 * Не се препоръчва.
 * Ако в рекурсията има индексиране, то нещо не е наред.
 */
bool contains2(const int* a, int n, int x, int i) {
	if(i == n) {
		return false;
	}
	return a[i] == x || contains2(a, n, x, i + 1);
}

/**
 * Чисто-рекурсивен: красив код.
 * По-сложен е за разбиране.
 * Кратък и изчистен.
 * По-бавен от итеративният подход.
 */
bool contains3(const int* a, int n, int x) {
	if(n < 1) {
		return false;
	}
	return a[n - 1] == x || contains3(a, n - 1, x);
}

int main() {

	int a[5] = {102, 280, 94, 294, 98};
	int x = 98;
	cout << "Iterative: " << (contains(a, 5, x) ? "true" : "false") << endl;
	cout << "Pseudo-recursive: " << (contains2(a, 5, x, 0) ? "true" : "false") << endl;
	cout << "Recursive: " << (contains3(a, 5, x) ? "true" : "false") << endl;

	return 0;
}
