#include <stdio.h>

/*
prva dva elementa: 1 1
svaki sledeci je zbir prethodnih: 1 1 2 3 5 8 13 21...
                      pozicija:   0 1 2 3 4 5 6  7

pisemo rekurzivnu fju koja racuna n-ti fibonacijev broj, tj. broj na poziciji n
 */

int fib(int n){
  // sada imamo dva izlaza iz rekurzije
  if (n <= 1)
    return 1;
  else
    // i dva rekurzivna poziva
    return fib(n-1) + fib(n-2);
}

/*
   ovo je samo primer rekurzivnog poziva ali nije efikasan
   ova fja nije efikasna jer fib(n-1) poziva fib(n-2) i fib(n-3)
   fib(n-2) poziva fib(n-3) i fib(n-4)


npr: n = 4

          f(4)
       /       \
      f(3)     f(2)
    /   \     /    \
   f(2) f(1) f(1)  f(0)
  / \     |   |     |
f(1) f(1) 1   1     1
 |   |
 0   0

 */

/*
  Posto se sva racunanja svaki put izvode od pocetka, nista se ne pamti.
  Ponavljanje puno izracunavanja.
  Bolje resenje bi bilo da se napise nerekurzivna fja preko petlje
 */

int fib_it(int n){
  int prvi = 1;
  int drugi = 1;
  int tekuci; // suma prethodna dva

  for(int i=1; i<=n; i++){
    tekuci = prvi + drugi;
    // 1     2      3     4 --- pozicije
    // 1     1      2     3 --- vrednosti
    // prvi, drugi, tekuci
    // ... , prvi , drugi
    prvi = drugi;
    drugi = tekuci;
  }
  return prvi;
}

int main(int argc, char* argv[]){
  int x;
  scanf("%d", &x);
  printf("Fibonacijev broj na poziciji %d je %d\n", x, fib(x));
  printf("Iterativno broj na poziciji %d je %d\n", x, fib_it(x));
  return 0;
}