Python Fibonacci đệ quy

Cách thứ nhất là kiểu vũ phu. Cách thứ hai cố gắng giảm các lệnh gọi hàm trong đệ quy

Ưu điểm của đệ quy là chương trình trở nên biểu cảm

ví dụ 1. Tạo chuỗi Fibonacci bằng cách sử dụng đệ quy trong Python

Trong ví dụ này, chúng tôi viết một hàm tính toán phần tử thứ _____ của chuỗi Fibonacci bằng cách sử dụng đệ quy

Chương trình Python

def fibonacci[n]:
	if npython example.py
Enter a number, N, N>=2 : 10
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

D:\>python example.py
Enter a number, N, N>=2 : 5
[0, 1, 1, 2, 3]

Giới thiệu về hiệu suất

Nếu bạn xem xét hiệu suất, đây là một sai lầm. Tại sao? . Hãy bỏ qua cuộc thảo luận về việc tạo ngăn xếp cho mỗi lệnh gọi hàm trong hàm. Khi bạn đang tính toán phần tử Fibonacci thứ n, tất cả các phần tử Fibonacci trước phần tử thứ n phải được tính toán lại, bất kể thực tế là chúng ta đã tính toán chúng

ví dụ 2. Tạo Chuỗi Fibonacci bằng cách sử dụng Đệ quy trong Python [Cải thiện]

Trong ví dụ này, chúng tôi xem xét thực tế là các phần tử thứ 0, 1, 2, . ., i-1 trước đó đã được tính toán khi bạn đang tạo phần tử thứ i

Chương trình Python

fibo_series = [0, 1]

def fibonacci[n]:
	if n0:
		return fibo_series[n-1]
	else:
		fn = fibonacci[n-1] + fibonacci[n-2]
		if n>len[fibo_series]:
			fibo_series.append[fn]
		return fn

n = int[input['Enter a number, N, N>=2 : ']]

fibonacci[n]

print[fibo_series]

đầu ra

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

Bản tóm tắt

Trong hướng dẫn Ví dụ về Python này, chúng ta đã học cách tạo Chuỗi Fibonacci trong Python bằng kỹ thuật Đệ quy

Trước khi tìm hiểu cách tạo dãy Fibonacci trong python bằng đệ quy, trước tiên chúng ta hãy tìm hiểu sơ qua về dãy Fibonacci

Chuỗi Fibonacci là một chuỗi số toán học bắt đầu bằng các số cố định 0 và 1. Tất cả các số sau đây có thể được tạo bằng cách sử dụng tổng của hai số cuối cùng. Tham khảo hình bên dưới để hiểu rõ hơn

Như thể hiện trong sơ đồ trên, hai chữ số đầu tiên được cố định, tôi. e. ,0 và 1. Thuật ngữ thứ ba được tính bằng cách sử dụng hai thuật ngữ cuối cùng i. e 1=[1+0]1 = [1 + 0]1=[1+0]. Một lần nữa, chúng ta tính số hạng thứ tư bằng cách cộng các số hạng thứ hai và thứ ba, i. e. , 2=[1+1]2 = [1 + 1]2=[1+1]

Tham khảo tại đây để tìm hiểu thêm về dãy Fibonacci

Chuỗi Fibonacci có thể được tính theo nhiều cách, chẳng hạn như

• Sử dụng lập trình động
• Sử dụng vòng lặp
• Sử dụng đệ quy

Hãy để chúng tôi tìm hiểu cách tạo chuỗi Fibonacci trong python bằng cách sử dụng đệ quy

Thứ tự của chuỗi Fibonacci là
0,1,1,2,3,5,8,13,21,34,55,89,144,. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,. 0,1,1,2,3,5,8,13,21,34,55,89,144,

Chúng ta có thể thấy rằng một thuật ngữ [giả sử thuật ngữ thứ nthnthn] có thể được tính bằng hai thuật ngữ cuối cùng. Thuật ngữ thứ nnn có thể được tính bằng hai thuật ngữ cuối cùng i. e. [n−1]th[n - 1]th[n−1]th và [n−2]th[n - 2]th[n−2]số hạng

Chúng ta có thể xây dựng trình tự này như

Tên chức năng. fibonacci[N]

Mã giả cho cách tiếp cận đệ quy có thể là

Begin
    if n == 0 then
        return 0
    else if n == 1 then
        return 1
    else
        return fibonacci[N - 1] + fibonacci[N - 2]
    endif
End
Tham khảo phần ví dụ bên dưới để triển khai mã
Ví dụ
Chúng ta biết rằng hai số hạng đầu tiên của dãy Fibonacci là cố định, i. e. , 0 và 1. Giả sử chúng ta muốn tạo số hạng thứ 7 của dãy Fibonacci
Số hạng thứ 7 có thể được tính bằng tổng của số hạng thứ 5 và thứ 6. Nhưng cả nhiệm kỳ thứ 5 và thứ 6 hiện chưa rõ
Tương tự, ta có thể tính số hạng thứ 5 bằng cách cộng số hạng thứ 4 và thứ 3. Chúng ta có thể hình dung các lệnh gọi đệ quy này dưới dạng cấu trúc cây được hiển thị bên dưới
[IMAGE_2 Sử dụng cùng một hình ảnh]
Việc triển khai mã giống nhau
def fibonacci[N]:
    if N == 0:
        return 0

    elif N == 1:
        return 1

    # The above two if statements can be combined as:
    # if N