// 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));
}
}
