/* Ohjelmassa etsitään n:s luku Fibonaccin sarjasta
	Algoritmi: fib(n) = fib(n - 2) + fib(n - 1)
	Lopetusehto: n = 2 || n = 1
	Ratkaisussa käytetään rekursiota.*/

#include <stdio.h>
int fib(int n);

/*pääohjelma, jossa kutsutaan rekursiivista funktiota*/

void main()
{
  int n, vastaus;
  printf("Anna etsittävän luvun positio\n");
  scanf("%d", &n);

  vastaus = fib(n);

  printf("\n\nFibonaccin sarjan %d luku on %d\n", n, vastaus);
}

int fib(int n)
{
  printf("Lasketaan fib %d ...",n);

  if (n < 3)
  {
    printf("Palautetaan 1 !\n");
    return (1);
  } 
  else
  {
    printf("Tehdään kutsut fib(%d) ja fib(%d)\n", n-2, n-1);
    return (fib(n-2) + fib(n-1));
  }
}