Cơ sở lý thuyết của dãy Fibonacci như sau:
– Dãy fibonacci: 1,1,2,3,5,8,13,21,34,55…
– Bước cơ sở: f(0) =1, f(1) = 1
– Bước đệ qui: f(n)= f(n-1) + f(n-2)
Thuật toán in dãy số Fibonacci đã được trình bày trong phần thuật toán số học. Tuy nhiên, đây cũng là bài toán có thể biểu diễn bằng phương pháp đệ quy, nên trong bài học này chúng ta sẽ biểu diễn lại bài toán này bằng thuật toán đệ quy.

Yêu cầu: Một số n sau đó in ra chữ số thứ n trong dãy Fibonacci.

Dữ liệu: nhập dữ liệu gồm

• Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 10^6).

Kết quả: vị trí số của n trong dãy Fibonacci