Dãy số Fibonacci được định nghĩa như sau:

• ~F₁ = 0~
• ~F₂ = 1~
• ~Fₙ = Fₙ₋₁ + Fₙ₋₂~ với ~n > 2~

Hãy tìm số Fibonacci thứ ~n~ bằng phương pháp đệ quy.

Lưu ý:

Độ phức tạp của cách làm đệ quy trực tiếp là khoảng:

~O(1.618ⁿ)~

nên không phù hợp với các giá trị ~n~ lớn.

Dữ liệu vào

• Dòng duy nhất chứa số nguyên dương ~n~.

Ràng buộc

• ~1 ≤ n ≤ 15~.

Kết quả

In ra số Fibonacci thứ ~n~.

Ví dụ

Dữ liệu vào

1

Kết quả

0

Giải thích

Theo định nghĩa:

~F₁ = 0~

nên số Fibonacci thứ ~1~ là ~0~.