/*
a) Napisati rekurzivnu funkciju koja racuna (i,j)-ti element Paskalovog trougla. Izracunati slozenost.
b) Napisati rekurzivnu funkciju koja racuna zbir n-tog reda Paskalovog trougla.

Primer Paskalovog trougla:
	 1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1
1 5 10 10 5 1
*/

#include <stdio.h>

// suma n-tog reda jednaka je 2*suma_prethodnog_reda (jer svaki element iz prethodnog reda uzimamo dva puta pri racunanju zbira, jer je svaki
// element datog reda jednak zbiru dva element iznad njega
int suma(int n)
{
	if (n==1) return 1;
	else return 2*suma(n-1);
}

int element(int i, int j)
{
	if (i==1 && j==1) return 1;
	else if (j==1) return 1;
	     else if (i==j) return 1;
		      else return element(i-1,j)+element(i-1,j-1);
}

int main()
{
	int n, i, j;

	printf("Unesi n:\n");
	scanf("%d", &n);
	
	printf("Suma je %d\n", suma(n));
	
	printf("Uneti indekse i i j:\n");
	scanf("%d%d", &i, &j);
	
	printf("Trazeni element je %d\n", element(i,j));

	return 0;
}

/*
Svaki i-ti red ima tacno i elemenata, pa kod elementa sa indeksom(i,j) uvek vazi j <= i; to znaci da je i dominantno i ono nam utice na slozenost.

Drugim recima, element(i,j) se ocitava kao j-ta vrednost u i-toj vrsti 
Paskalovog trougla. Paskalov trougao sa i vrsta ima povrsinu 1 + 2 + 3 + ... + i, sto je i(i+1)/2, 
drugim recima O(i^2), tako da kad izracunamo 
i-tu vrstu treba izdvojiti j-ti element i-te vrste, te je ukupna slozenost 
O(i^2 + j), ali posto znamo da je j <= i, onda je to takodje O(i^2 + i), 
pa samim tim i O(i^2).
*/