class Stack
{
	Object[] elements;
	int top;

	public Stack(int size)
	{
		elements = new Object[size];
		top = -1;
	}

	public boolean isEmpty()
	{
		return top == -1;
	}

	public boolean isFull()
	{
		return top == elements.length-1;
	}

	public Object top()
	{
		if (isEmpty()) // error: throw new UnderflowException
			return null;
		else
			return elements[top] ;
	}

	public void push(Object e)
	{
		if (isFull()) //error: throw new OverflowException
			;
		else
		{
			top++;
			elements[top] = e;
		}
	}

	public void pop()
	{
		if (isEmpty()) // error: throw new UnderflowException
			;
		else top--;
	}
}



public class recToIter {

	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//
	// NALOGA 1:
	//
	// Podana je (naivna) rekurzivna funkcija za izracun n-tega Fibonaccijevega stevila.
	//
	// Spremeni podano rekurzivno funkcijo v iterativno z uporabo sklada.
	//
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

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

//	public static int fibRek(int n) {
//		if (n <= 2)
//			return 1;
//		else {
//			int tmp1 = fibRek(n-1);
//			int tmp2 = fibRek(n-2);
//			return tmp1 + tmp2;
//		}
//	}


	public static int fibIterStack(int n)
	{
		class StackElement
		{
			int n;
			int temp1;
			int temp2;
			int address;

			public StackElement() {}
			public StackElement(StackElement e)
			{
				n = e.n;
				temp1 = e.temp1;
				temp2 = e.temp2;
				address = e.address;
			}
		}

		Stack s = new Stack(100); //100 ugnzdenih klicev se pozre
		StackElement e = new StackElement();
		e.n = n;
		e.address = 0;
		s.push(e);
		int result = 0; //ker je nasa funkcija int torej more neke vracat

		//simulacija izvedbe
		do
		{
			e = (StackElement) s.top(); //morem castat, ker ti vrne sam objekt, ker je splosna implementacija za sklad
			s.pop();
			switch (e.address)
			{
				case 0:
					if(e.n <= 2)
					{
						result = 1;
						break;
					}
					else
					{
						//rabimo zapis kam bomo skocli v globino in kam pol nazaj
						//prvo damo mesto povratka pol pa skoka notr v sklad, ker first in last out
						e.address = 1; //dam na sklad
						s.push(new StackElement(e)); //ne bom dala e, ker hocem v skladu neodvisen zapis, da ceprov tle spreminjam e, se v skladu ne spreminja, zato kopijo nrdim
						e.n--;
						e.address = 0; //zj to dam na sklad
						s.push(new StackElement(e));
						break;
					}

				case 1:
					//zdej smo prsli vn iz rekurzije in morem v temp shrant rez
					e.temp1 = result;
					//zdej morem v durgo rekurijo it
					e.address = 2;
					s.push(new StackElement(e));
					e.n -= 2;
					e.address = 0;
					s.push(new StackElement(e));
					break;

				case 2:
					//prsli iz druge rekurzije
					e.temp2 = result;
					result = e.temp1 + e.temp2;
					break;
			}
		} while (!s.isEmpty());

		return result;
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//
	// NALOGA 2:
	//
	// Celi del logaritma nekega stevila se racuna tako, da se presteje, kolikokrat je treba stevilo (celostevilcno) deliti
	// z osnovo logaritma, da stevilo postane manjse od osnove.
	//
	// a) Sestavi iterativno funkcijo za racunanje celega dela logaritma danega stevila n pri osnovi b.
	//
	// b) Sestavi rekurzivno funkcijo za racunanje celega dela logaritma danega stevila n pri osnovi b.
	//
	// c) Spremeni rekurzivno verzijo iz naloge b) v iterativno z uporabo sklada.
	//
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	public static int celiDelLogIter(double n, double b)
	{
		// Dopolnite kodo

		return 0;
	}

	public static int celiDelLogRek(double n, double b)
	{
		// Dopolnite kodo

		return 0;
	}

	public static int celiDelLogIterStack(double n, double b)
	{
		// Dopolnite kodo

		return 0;
	}


	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//
	// NALOGA 3:
	//
	// Spremeni rekurzivno funkcijo "nadaljujIzrazRek" v iterativno z uporabo sklada.
	//
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	public static void nadaljujIzrazRek(int ukl, int zak, char[] izraz, int n) {
		if (zak == 0) {
			System.out.println(izraz);
			return;
		}

		if (ukl > 0) {
			izraz[n] = '(';
			nadaljujIzrazRek(ukl-1, zak, izraz, n+1);
		}

		if (zak > ukl) {
			izraz[n] = ')';
			nadaljujIzrazRek(ukl, zak-1, izraz, n+1);
		}
	}

	public static void nadaljujIzrazIterStack(int ukl, int zak, char[] izraz, int n)
	{
		// Dopolnite kodo

	}



	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	//
	// NALOGA 4:
	//
	// Spremeni rekurzivno funkcijo "sestaviRek" v iterativno z uporabo sklada.
	//
	///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

	public static boolean sestaviRek(int[] vrednosti, int index, int znesek) {
		if (znesek == 0)
			return true;

		if (znesek < 0)
			return false;

		if (index >= vrednosti.length)
			return false;

		if (sestaviRek(vrednosti, index+1, znesek - vrednosti[index])) {
			System.out.print(vrednosti[index] + ", ");
			return true;
		}
		else
			return sestaviRek(vrednosti, index+1, znesek);
	}

	public static boolean sestaviIterStack(int[] vrednosti, int index, int znesek)
	{
		// Dopolnite kodo

		return false;
	}



	public static void main(String[] args)
	{
		System.out.println("NALOGA 1\n");
		System.out.println("Rekurzivna verzija: osmo Fibonaccievo stevilo je " + fibRek(8));
		System.out.println("Iteracija s skladom: osmo Fibonaccievo stevilo je " + fibIterStack(8));


		double n = 12.876;
		double b = 1.587;

		System.out.println("\n\n\nNALOGA 2\n");
		System.out.println("Iterativna verzija: celi del logaritma stevila " + n + " pri osnovi " + b + " je " + celiDelLogRek(n,b));
		System.out.println("Rekurzivna verzija: celi del logaritma stevila " + n + " pri osnovi " + b + " je " + celiDelLogIter(n,b));
		System.out.println("Iteracija s skladom: celi del logaritma stevila " + n + " pri osnovi " + b + " je " + celiDelLogIterStack(n,b));


		System.out.println("\n\n\nNALOGA 3\n");
		char[] izraz = new char[6];

		System.out.println("Rekurzivna verzija:");
		nadaljujIzrazRek(3, 3, izraz, 0);
		System.out.println("\nIteracija s skladom:");
		nadaljujIzrazIterStack(3, 3, izraz, 0);

		System.out.println("\n\n\nNALOGA 4\n");
		int[] vrednosti = {8,5,1,3,4};
		int znesek = 10;

		System.out.println("Rekurzivna verzija:");
		System.out.print("Znesek " + znesek + " dobimo tako, da sestejemo elemente: ");

		if (!sestaviRek(vrednosti, 0, znesek))
			System.out.println("Zneska ni mogoce sestaviti s podanimi elementi");
		else
			System.out.println();

		System.out.println("\nIteracija s skladom:");
		System.out.print("Znesek " + znesek + " dobimo tako, da sestejemo elemente: ");

		if (!sestaviIterStack(vrednosti, 0, znesek))
			System.out.println("Zneska ni mogoce sestaviti s podanimi elementi");
		else
			System.out.println();
	}

}