Dãy số fibonacci là dãy số được tạo bằng cách như sau:

• Hai số đầu tiên là số 1.
• Các số tiếp theo lần lượt được tạo thành từ tổng của 2 số trước nó.
• Dãy fibonacci: 1, 1, 2, 3, 5, 8, 13, 21, ...

Nhập vào một số nguyên dương n, hãy đưa ra số fibonacci thứ n. Hãy thực hiện điều đó bằng giải thuật đệ quy.

Ví dụ:

• Test mẫu 1:
   

  Input	Output
  4	3

  
  Với n = 4 thì kết quả mong muốn là 3.
   
• Test mẫu 2:
   

  Input	Output
  7	13

  
  Với n = 7 thì kết quả mong muốn là 13.

Hướng dẫn bài tập.

Ý tưởng:

Theo đề bài ta nhận ra rằng fibo(n) = fibo(n-1) + fibo(n-2). Điều kiện cơ bản là khi n = 1 hoặc n = 2 thì hàm trả về 1.

long long fibonacci(int n){
	if (n == 1 || n == 2) return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

long long fibonacci(int n){
	if (n == 1 || n == 2) return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}
int main(){
	int n;
	cin >> n;
	cout << fibonacci(n);
	return 0;
}