public class Solution { public int Fibonacci(int n) { if(n < 1) return 0; if(n == 1 || n == 2) return 1; return Fibonacci(n-1) + Fibonacci(n-2); } }