// Time Complexity: O(2^n), Auxiliary Space: O(N).
// Fibonacci Series using Recursion

class fibonacci
{
	static int fib(int n)
	{
      // if (n == 0) return 0;
      // if (n == 1) return 1;
      if (n <= 1)
      	return n;
      
      return fib(n-1) + fib(n-2);
	}
	
	public static void main (String args[])
	{
      int n = 9;
      System.out.println(fib(n));
	}
}