Bạn gọi def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)6. Điều này kiểm tra xem def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)7, điều này có đúng hay không, do đó, nó gọi def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)8 (45 - 10), mà không trả lại kết quả của nó. Điều tương tự cũng xảy ra với def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)9 và def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))0, cho đến khi cuối cùng def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))1 được gọi. Show
Điều này in 'Giá trị thực 5', và sau đó trả về 5. Nhưng trả về kết quả từ một hàm luôn trả lại cho người gọi trực tiếp của hàm này. Nó không nhảy ngay lập tức thông qua một số cuộc gọi; Rốt cuộc, người gọi có thể muốn làm một cái gì đó với kết quả đã trả lại trước khi trả lại một cái gì đó cho người gọi. Mặc dù vậy, trong trường hợp này, chỉ có def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))1 trả lại bất cứ điều gì; Tất cả những người khác gọi def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))3, chờ điều đó trở lại, bỏ qua bất cứ điều gì nó làm lại, và sau đó (ngầm) trả lại def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))4. Vì lời mời ngoài cùng def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)6 là một trong những trường hợp này, những gì bạn nhận được là def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))4.always returns it to the direct caller of this function. It doesn't jump immediately out through several calls; after all, the caller might want to do something with the returned result before returning something to it's caller. In this case though, only def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))1 returns anything at all; all the others call def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))3, wait for that to return, ignore whatever it does return, and then (implicitly) return def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))4. Since the outermost invocation def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)6 is one of these cases, what you get is def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))4. Đây là một nỗ lực để hình dung về những gì xảy ra: Bạn đã không gọi def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))1 trong trình thông dịch, def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))1 được gọi từ bên trong một cuộc gọi chức năng khác. Vì vậy, lợi nhuận từ def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))1 đi đến cuộc gọi chức năng đó. Thực tế là đây là một chức năng tự gọi là hoàn toàn không liên quan. Bạn sẽ nhận được chính xác kết quả tương tự nếu mã của bạn trông như thế này: Hàm kiểm tra (x) bạn gọi với 'x = 45' giống như gọi factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1200. Tôi hy vọng bạn có thể thấy lý do tại sao rõ ràng là def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))4 nên được trả lại khi đệ quy không liên quan. Vâng, khi đệ quy có liên quan, không có gì thay đổi. Tuyên bố factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1202 không biết và không quan tâm liệu nó có trở lại từ một chức năng được gọi đệ quy hay không, nó hoạt động chính xác theo cùng một cách trong cả hai trường hợp. Trên thực tế, đệ quy không phải là bất cứ điều gì "đặc biệt"; Nó hành xử chính xác giống như các cuộc gọi chức năng thông thường. Bạn nhận được thông tin từ những thứ gọi bạn qua các đối số và bạn trả lại thông tin cho những thứ gọi bạn bằng cách trả lại. Nếu bạn không trả lại một cái gì đó (có lẽ chỉ trong một nhánh của factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1203), thì def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5))4 sẽ được trả lại cho người gọi của bạn, bất kể bạn có gọi bất kỳ chức năng nào khác trong chi nhánh đó, bất kể chức năng đó có thể trả lại gì nếu bạn gọi Một cái gì đó, và bất kể chức năng bạn gọi có phải là cùng một chức năng mà bạn đang ở bên trong hay không. Bởi Bernd Klein. Sửa đổi lần cuối: 01 tháng 2 năm 2022.Bernd Klein. Last modified: 01 Feb 2022. Trên trang này➤ Sự định nghĩaĐệ quy có liên quan đến vô cùng. Tôi biết đệ quy có liên quan đến vô cùng. Tôi nghĩ rằng tôi biết đệ quy có liên quan đến vô cùng. Anh ấy chắc chắn tôi nghĩ rằng tôi biết đệ quy có liên quan đến vô cùng. Chúng tôi nghi ngờ anh ấy chắc chắn tôi nghĩ rằng tôi biết ... Chúng tôi nghĩ rằng, bạn nghĩ, chúng tôi đã thuyết phục bạn bây giờ rằng, chúng tôi có thể tiếp tục mãi mãi với ví dụ này về một đệ quy từ ngôn ngữ tự nhiên. Đệ quy không chỉ là một đặc điểm cơ bản của ngôn ngữ tự nhiên, mà còn về năng lực nhận thức của con người. Cách suy nghĩ của chúng tôi dựa trên một quá trình tư duy đệ quy. Ngay cả với một quy tắc ngữ pháp rất đơn giản, như "một câu tiếng Anh chứa một chủ đề và vị ngữ, và một vị ngữ chứa một động từ, một đối tượng và một bổ sung", chúng ta có thể chứng minh các khả năng vô hạn của ngôn ngữ tự nhiên. Nhà khoa học nhận thức và nhà ngôn ngữ học Stephen Pinker cụm từ như thế này: "Với vài nghìn danh từ có thể lấp đầy vị trí chủ đề và vài nghìn động từ có thể lấp đầy vị trí, người ta đã có vài triệu cách để mở một câu. Nhanh chóng nhân lên với số lượng lớn không thể tưởng tượng được. Thật vậy, tiết mục của các câu là vô hạn về mặt lý thuyết, bởi vì các quy tắc của ngôn ngữ sử dụng một mẹo gọi là đệ quy. Một quy tắc đệ quy cho phép một cụm từ chứa một ví dụ về chính nó, vì cô nghĩ rằng anh ta nghĩ rằng họ nghĩ rằng anh ta biết và cứ thế, quảng cáo. Và nếu số lượng câu là vô hạn, số lượng suy nghĩ và ý định có thể cũng là vô hạn, bởi vì hầu như mọi câu đều thể hiện một suy nghĩ hoặc ý định khác nhau. "1  Chúng ta phải dừng chuyến tham quan ngắn của mình để sử dụng đệ quy trong ngôn ngữ tự nhiên để quay lại đệ quy trong khoa học máy tính và các chương trình và cuối cùng là đệ quy trong ngôn ngữ lập trình Python. Tính từ "đệ quy" có nguồn gốc từ động từ Latin "tái phát", có nghĩa là "chạy lại". Và đây là những gì một định nghĩa đệ quy hoặc một hàm đệ quy làm: nó đang "chạy trở lại" hoặc quay trở lại chính nó. Hầu hết những người đã thực hiện một số toán học, khoa học máy tính hoặc đọc một cuốn sách về lập trình sẽ gặp phải sự kiện, được định nghĩa theo thuật ngữ toán học là n! = n * (n-1)!, if n > 1 and 0! = 1 Nó được sử dụng thường xuyên như một ví dụ cho đệ quy vì sự đơn giản và rõ ràng của nó. Định nghĩa của đệ quyĐệ quy là một phương pháp lập trình hoặc mã hóa một vấn đề, trong đó một hàm tự gọi mình là một hoặc nhiều lần trong cơ thể của nó. Thông thường, nó đang trả về giá trị trả về của cuộc gọi chức năng này. Nếu một định nghĩa hàm thỏa mãn điều kiện đệ quy, chúng ta gọi hàm này là hàm đệ quy. Điều kiện chấm dứt: Một hàm đệ quy phải đáp ứng một điều kiện quan trọng sẽ được sử dụng trong một chương trình: nó phải chấm dứt. Một hàm đệ quy chấm dứt, nếu với mỗi cuộc gọi đệ quy, giải pháp của vấn đề bị thu hẹp và di chuyển về phía một trường hợp cơ sở. Một trường hợp cơ sở là một trường hợp, trong đó vấn đề có thể được giải quyết mà không cần đệ quy thêm. Một đệ quy có thể kết thúc trong một vòng lặp vô hạn, nếu trường hợp cơ sở không được đáp ứng trong các cuộc gọi. Example: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 1 Thay thế các giá trị được tính toán cho chúng ta biểu thức sau 4! = 4 * 3 * 2 * 1 Nói cách khác, đệ quy trong khoa học máy tính là một phương pháp trong đó giải pháp cho một vấn đề dựa trên việc giải quyết các trường hợp nhỏ hơn của cùng một vấn đề. Các chức năng đệ quy trong PythonBây giờ chúng tôi đến để thực hiện giai thừa trong Python. Nó dễ dàng và thanh lịch như định nghĩa toán học. def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) Chúng ta có thể theo dõi cách hoạt động của hàm bằng cách thêm hai hàm in () vào định nghĩa chức năng trước đó:
def factorial(n): print("factorial has been called with n = " + str(n)) if n == 1: return 1 else: res = n * factorial(n-1) print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) return res print(factorial(5)) OUTPUT:factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 120 Chúng ta hãy xem một phiên bản lặp của chức năng giai thừa. def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i)) OUTPUT:Đó là thực tế phổ biến để mở rộng chức năng giai thừa cho 0 như một đối số. Thật hợp lý khi định nghĩa factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1205 là factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1206, bởi vì có chính xác một hoán vị của các đối tượng bằng không, tức là nếu không có gì là để hoán vị, "mọi thứ" đều được đặt tại chỗ. Một lý do khác là số lượng cách chọn n phần tử trong số một bộ N được tính là N! chia cho sản phẩm của N! và 0 !. Tất cả những gì chúng ta phải làm để thực hiện điều này là thay đổi điều kiện của câu lệnh IF: def factorial(n): if n == 0: return 1 else: return n * factorial(n-1) Đào tạo Python sống Các khóa học trực tuyến sắp tới Ghi danh ở đây Số FibonacciChuyên luận về đệ quy của chúng tôi dẫn chúng ta đến một trường hợp thú vị khác về đệ quy. Có những gì có hoa hướng dương, tỷ lệ vàng, hình nón cây linh sam, mã da vinci, bài hát "lateralus" theo công cụ và đồ họa ở phía bên phải? Phải, các số fibonacci. Chúng tôi không giới thiệu các số Fibonacci, bởi vì chúng là một ví dụ hữu ích khác cho chức năng tái kết hợp. Cố gắng viết một hàm đệ quy cho chuỗi số này, có thể dẫn đến một chương trình không hiệu quả. Trong thực tế, không hiệu quả đến nỗi nó sẽ không hữu ích. Chúng tôi giới thiệu các số Fibonacci để cho bạn thấy những cạm bẫy của đệ quy. Các số Fibonacci là số của chuỗi các giá trị số nguyên sau: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Các số Fibonacci được xác định bởi: $ F_n = f_ {n-} + f_ {n-2} $ Với $ f_0 = 0 $ và $ f_1 = 1 $ Trình tự Fibonacci được đặt theo tên của nhà toán học Leonardo của Pisa, người được biết đến nhiều hơn là Fibonacci. Trong cuốn sách "Liber Abaci" (xuất bản năm 1202), ông đã giới thiệu trình tự như một bài tập thể dục liên quan đến Bunnies. Trình tự của anh ấy về các số Fibonacci bắt đầu bằng F1 = 1, trong khi trong toán học hiện đại, chuỗi bắt đầu bằng F0 = 0. Nhưng điều này không ảnh hưởng đến các thành viên khác của chuỗi. Các số Fibonacci là kết quả của một quần thể thỏ nhân tạo, thỏa mãn các điều kiện sau:
Các số Fibonacci là số lượng của các cặp thỏ sau factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1207 tháng, tức là sau 10 tháng, chúng tôi sẽ có Rabit $ F_10 $. Các số Fibonacci rất dễ viết dưới dạng hàm Python. Nó ít nhiều là một đến một ánh xạ từ định nghĩa toán học: Một giải pháp lặp cũng dễ viết, mặc dù giải pháp đệ quy trông giống như định nghĩa: Chúng tôi sẽ viết một mô -đun với tên factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1208 chứa cả funciton factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1209 và def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))0. Để làm điều này, bạn phải sao chép mã sau vào một tệp có tên fibonacci0.py: OUTPUT:Nếu bạn kiểm tra các hàm fib () và fibi (), bạn sẽ phát hiện ra rằng phiên bản lặp fibi () nhanh hơn rất nhiều so với phiên bản đệ quy (). Để có được một ý tưởng về việc "nhanh hơn rất nhiều" này có thể, chúng tôi đã viết một kịch bản, sử dụng mô -đun thời gian, để đo các cuộc gọi. Để làm điều này, chúng tôi lưu các định nghĩa chức năng cho FIB và FIBI trong một tệp fibonacci.py, chúng tôi có thể nhập trong chương trình (fibonacci_runit.py) bên dưới: OUTPUT:def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))1 là thời gian tính bằng vài giây cho 3 cuộc gọi đến def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))2 và def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))3 tương ứng là thời gian cho def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))4. Có gì sai với việc thực hiện đệ quy của chúng tôi? Chúng ta hãy xem cây tính toán, tức là thứ tự được gọi là các chức năng. FIB () được thay thế bởi f (). Chúng ta có thể thấy rằng Subtree F (2) xuất hiện 3 lần và người con để tính toán F (3) hai lần. Nếu bạn tưởng tượng việc mở rộng cây này cho F (6), bạn sẽ hiểu rằng F (4) sẽ được gọi là hai lần, F (3) ba lần, v.v. Điều này có nghĩa là, đệ quy của chúng tôi không nhớ các giá trị được tính toán trước đó. Chúng tôi có thể triển khai "bộ nhớ" cho phiên bản đệ quy của mình bằng cách sử dụng từ điển để lưu các giá trị được tính toán trước đó. Chúng tôi gọi phiên bản này def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))5: Trước khi chúng tôi có thể thực hiện một số thời gian trên phiên bản mới, chúng tôi thêm nó vào mô -đun factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1208 của chúng tôi: OUTPUT:Chúng tôi đã hết thời gian để so sánh nó với Fibi (): OUTPUT:Chúng ta có thể thấy rằng nó thậm chí còn nhanh hơn phiên bản lặp. Tất nhiên, các lập luận càng lớn, lợi ích của chúng tôi càng lớn: Chúng tôi cũng có thể xác định thuật toán đệ quy cho hàm Fibonacci của chúng tôi bằng cách sử dụng một lớp có các phiên bản Callabe, tức là bằng cách sử dụng lệnh gọi phương thức đặc biệt. Bằng cách này, chúng ta sẽ có thể che giấu từ điển một cách thanh lịch. Chúng tôi đã sử dụng một cách tiếp cận chung cho phép xác định các chức năng cũng tương tự như Fibonacci, như hàm Lucas. Điều này có nghĩa là chúng ta có thể tạo các chuỗi số giống như Fibonacci bằng cách khởi tạo các trường hợp của lớp này. Về cơ bản, nguyên tắc xây dựng, tức là tổng của hai số trước, sẽ giống nhau. Chúng sẽ khác nhau bởi hai giá trị ban đầu:call. This way, we will be able to hide the dictionary in an elegant way. We used a general approach which allows as to define also functions similar to Fibonacci, like the Lucas function. This means that we can create Fibonacci-like number sequences by instantiating instances of this class. Basically, the building principle, i.e. the sum of the previous two numbers, will be the same. They will differ by the two initial values: n! = n * (n-1)!, if n > 1 and 0! = 10 OUTPUT:n! = n * (n-1)!, if n > 1 and 0! = 11 Sê -ri Số Lucas hoặc Lucas là một chuỗi số nguyên được đặt theo tên của nhà toán học François édouard Anatole Lucas (1842 Phản91), người đã nghiên cứu cả trình tự đó và các số Fibonacci liên quan chặt chẽ. Các số Lucas có quy tắc tạo giống như số Fibonacci, tức là tổng của hai số trước đó, nhưng các giá trị cho 0 và 1 là khác nhau. Trình tự Fibonacci tổng quátBây giờ chúng tôi sẽ chứng minh rằng cách tiếp cận của chúng tôi cũng phù hợp để tính toán các chuỗi Fibonacci tổng quát tùy ý. Trình tự Fibonacci phụ thuộc vào hai giá trị trước. Chúng tôi khái quát khái niệm này bây giờ bằng cách xác định chuỗi sợi K theo cách sau Cho một số tự nhiên cố định def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))7 và def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))8. Cũng được đưa ra def iterative_factorial(n): result = 1 for i in range(2,n+1): result *= i return result for i in range(5): print(i, iterative_factorial(i))7 Giá trị ban đầu $ I_0, I_1, \ ldots I_ {K-1} $ thỏa mãn $ f_k (0) = i_0, \ ldots f_k (k-1) = i_ {k-1} $ Chức năng cũng cần $ k $ Cofficents $ C_0, C_1, \ ldots C_ {K-1} $ $ F_k (n) $ được định nghĩa là $$ f_k (n) = a_0 \ cdot f_k (n-1) + a_1 \ cdot f_k (n-2) \ ldots a_ {k-1} \ cdot f_k (n-k) $$ $$ với $ k n! = n * (n-1)!, if n > 1 and 0! = 12 OUTPUT:n! = n * (n-1)!, if n > 1 and 0! = 11 Trình tự số pell bắt đầu bằng 1, 2, 5, 12, 29, ... Hàm là $ P (n) = 2 \ cdot p (n-1) + p (n-2) $ với $ p (0) = 1 $ và $ p (1) = 1 $ Thật dễ dàng để xây dựng chuỗi này với lớp def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)0 của chúng tôi: n! = n * (n-1)!, if n > 1 and 0! = 14 OUTPUT:n! = n * (n-1)!, if n > 1 and 0! = 15 Chúng ta có thể tạo một chuỗi thú vị khác bằng cách thêm tổng của hai số pell trước đó giữa hai số pell p (i) và p (i+1). Chúng tôi nhận được: $ P (0), p (1), p (0)+p (1), p (2), p (1)+p (2), p (3), p (2)+p (3) , \ ldots $ Tương ứng với: $ 1, 2, 3, 5, 7, 12, 17, 29, \ ldots $ n! = n * (n-1)!, if n > 1 and 0! = 16 OUTPUT:n! = n * (n-1)!, if n > 1 and 0! = 17 Nếu bạn có một cái nhìn cận cảnh về các con số, bạn có thể thấy rằng có một quy tắc khác trong chuỗi này. Chúng tôi có thể định nghĩa NP là $ np (n) = 2 \ cdot np (n-2) + np (n-4) $ với $ n> 3 $ và giá trị bắt đầu $ 1, 2, 3, 5 $ 5 $ Đây là một ứng dụng dễ dàng khác cho lớp def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)0 của chúng tôi: n! = n * (n-1)!, if n > 1 and 0! = 18 OUTPUT:n! = n * (n-1)!, if n > 1 and 0! = 17 Một thực tế toán học thú vị: Đối với mỗi số lẻ, chỉ số của $ p (n) $ by $ p (n-1) $ là một xấp xỉ $ \ sqrt {2} $. Nếu factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1207 chẵn, thương số là xấp xỉ $ 1 + {1 \ trên {\ sqrt {2}}} $ 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 10 OUTPUT:4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 11 Thông tin thêm về đệ quy trong PythonNếu bạn muốn tìm hiểu thêm về đệ quy, chúng tôi khuyên bạn nên cố gắng giải các bài tập sau. Vui lòng không nhìn vào các giải pháp, trước khi bạn cố gắng hết sức. Nếu bạn đã nghĩ về một nhiệm vụ trong một thời gian và bạn vẫn không có khả năng giải quyết bài tập, bạn có thể tham khảo các giải pháp mẫu của chúng tôi. Trong phần "Các chủ đề nâng cao" của hướng dẫn của chúng tôi, chúng tôi có một cách xử lý toàn diện về trò chơi hoặc câu đố "Tháp Hà Nội". Tất nhiên, chúng tôi giải quyết nó bằng một chức năng bằng cách sử dụng hàm đệ quy. "Vấn đề Hà Nội" là đặc biệt, bởi vì một giải pháp đệ quy gần như buộc chính nó lên lập trình viên, trong khi giải pháp lặp của trò chơi rất khó tìm và nắm bắt. Bài tậpBài tập 1Hãy nghĩ về một phiên bản đệ quy của hàm f (n) = 3 * n, tức là bội số của 3 Bài tập 2Viết một hàm Python đệ quy trả về tổng số N số nguyên đầu tiên. (Gợi ý: Hàm sẽ tương tự với chức năng giai thừa!) Bài tập 3Viết một chức năng thực hiện hình tam giác của Pascal: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 12 Bài tập 4Các số Fibonacci được ẩn bên trong tam giác của Pascal. Nếu bạn tổng hợp các số màu của tam giác sau, bạn sẽ nhận được số Fibonacci thứ 7: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 13 Viết một chương trình đệ quy để tính toán các số Fibonacci, sử dụng hình tam giác của Pascal. Bài tập 5Thực hiện một chức năng đệ quy trong Python cho sàng của Eratosthenes. Mây của Eratosthenes là một thuật toán đơn giản để tìm tất cả các số nguyên tố lên đến một số nguyên được chỉ định. Nó được tạo ra bởi các nhà toán học Hy Lạp cổ đại Eratosthenes. Thuật toán để tìm tất cả các số nguyên tố nhỏ hơn hoặc bằng với số nguyên đã cho N:
Bạn có thể dễ dàng thấy rằng chúng tôi sẽ không hiệu quả, nếu chúng tôi sử dụng nghiêm ngặt thuật toán này, ví dụ: Chúng tôi sẽ cố gắng loại bỏ bội số của 4, mặc dù chúng đã bị xóa bởi bội số của 2. Vì vậy, nó đủ để tạo ra bội số của tất cả các số nguyên tố lên đến căn bậc hai của n. Chúng ta có thể tạo ra các bộ này một cách đệ quy. Bài tập 6Viết một hàm đệ quy fib_indexfib (), trả về chỉ số của một số trong chuỗi fibonacci, nếu số là một phần tử của chuỗi này và trả về -1 nếu số không có trong đó, tức là. $ fib (Fib \ _index (n)) == N $ Bài tập 7Tổng của các hình vuông của hai số Fibonacci liên tiếp cũng là một số Fibonacci, ví dụ: 2 và 3 là các phần tử của chuỗi Fibonacci và 22 + 33 = 13 tương ứng với FIB (7). Sử dụng hàm trước để tìm vị trí của tổng các bình phương của hai số liên tiếp trong chuỗi Fibonacci. Giải thích toán học: Đặt A và B là hai số Fibonacci liên tiếp với A trước b. Trình tự Fibonacci bắt đầu với số "A" trông như thế này: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 14 Chúng ta có thể thấy rằng các số fibonacci xuất hiện dưới dạng các yếu tố cho a và b. Phần tử N-th trong chuỗi này có thể được tính toán với công thức sau: $ F (n) = fib (n-1) \ cdot a + fib (n) \ cdot b $ Từ điều này, chúng ta có thể kết luận rằng với số N, n> 1 tự nhiên, điều sau đây đúng: $ Fib (2 \ cdot n + 1) = fib (n)^2 + fib (n + 1)^2 $ Bài tập 8Các số Tribonacci giống như các số Fibonacci, nhưng thay vì bắt đầu với hai thuật ngữ được xác định trước, chuỗi bắt đầu bằng ba thuật ngữ được xác định trước và mỗi thuật ngữ sau đó là tổng của ba thuật ngữ trước. Một vài số đầu tiên của Tribonacci là:tribonacci numbers are like the Fibonacci numbers, but instead of starting with two predetermined terms, the sequence starts with three predetermined terms and each term afterwards is the sum of the preceding three terms. The first few tribonacci numbers are: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 15 Các số tetranacci bắt đầu với bốn thuật ngữ được xác định trước, mỗi thuật ngữ sau đó là tổng của bốn thuật ngữ trước đó. Một vài số Tetranacci đầu tiên là:tetranacci numbers start with four predetermined terms, each term afterwards being the sum of the preceding four terms. The first few tetranacci numbers are: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 16 Điều này tiếp tục theo cùng một cách đối với Pentanacci, Hexanacci, Heptanacci, Octanacci, v.v. Viết một chức năng cho các số Tribonacci và Tetranacci. Bài tập 9:Điều gì sẽ xảy ra nếu ai đó muốn kiểm tra các tham số trong một hàm đệ quy? Ví dụ chức năng giai thừa. Được rồi, xin vui lòng viết một phiên bản đệ quy của Factorial, trong đó kiểm tra các tham số. Có thể bạn đã làm điều đó một cách hoàn hảo, nhưng có lẽ không. Bạn có thể cải thiện phiên bản của bạn? Loại bỏ các bài kiểm tra không cần thiết? Các giải phápGiải pháp cho bài tập 1Về mặt toán học, chúng ta có thể viết nó như thế này: $ f (1) = 3, $ $ f (n + 1) = f (n) + 3 $ Một hàm Python có thể được viết như thế này: 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 17 OUTPUT:Giải pháp cho Bài tập 24! = 4 * 3! 3! = 3 * 2! 2! = 2 * 18 Giải pháp cho Bài tập 3: Tạo hình tam giác Pascal:4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 19 OUTPUT:Ngoài ra, chúng ta có thể viết một chức năng bằng cách sử dụng danh sách hiểu: 4! = 4 * 3 * 2 * 10 Đầu ra:Giải pháp cho Bài tập 4Sản xuất các số Fibonacci từ hình tam giác của Pascal: 4! = 4 * 3 * 2 * 11 OUTPUT:Giải pháp cho Bài tập 5Chương trình sau đây thực hiện sàng Eratosthenes theo các quy tắc của nhiệm vụ theo cách lặp lại. Nó sẽ in ra 100 số nguyên tố đầu tiên. 4! = 4 * 3 * 2 * 12 OUTPUT:4! = 4 * 3 * 2 * 13 Nhưng chương này trong hướng dẫn của chúng tôi là về các chức năng đệ quy và đệ quy, và chúng tôi đã yêu cầu một hàm đệ quy để tính toán các số nguyên tố. Để hiểu giải pháp sau, bạn có thể trao đổi chương của chúng tôi về việc hiểu danh sách: 4! = 4 * 3 * 2 * 14 OUTPUT:4! = 4 * 3 * 2 * 13 Giải pháp cho Bài tập 64! = 4 * 3 * 2 * 16 OUTPUT:4! = 4 * 3 * 2 * 17 Giải pháp cho Bài tập 8Chúng tôi sẽ sử dụng lớp def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)0 mà chúng tôi đã xác định trong chương này. 4! = 4 * 3 * 2 * 18 OUTPUT:4! = 4 * 3 * 2 * 19 def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)0 OUTPUT:def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)1 Chúng ta có thể dễ dàng tạo chúng như thế này: def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)2 OUTPUT:def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)3 Giải pháp cho Bài tập 9def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)4 Bạn nghĩ gì về giải pháp này? Bạn gọi def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)4 chẳng hạn. Funciton sẽ kiểm tra, nếu def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)5 là một số nguyên dương. Hàm sẽ gọi đệ quy def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)6. Trong cuộc gọi này, chức năng sẽ kiểm tra lại, nếu def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)7 là một số nguyên. nó có thể là gì khác? Cuộc gọi đầu tiên đã được kiểm tra def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)5 và tất cả những gì chúng tôi đã làm là trừ factorial has been called with n = 5 factorial has been called with n = 4 factorial has been called with n = 3 factorial has been called with n = 2 factorial has been called with n = 1 intermediate result for 2 * factorial( 1 ): 2 intermediate result for 3 * factorial( 2 ): 6 intermediate result for 4 * factorial( 3 ): 24 intermediate result for 5 * factorial( 4 ): 120 1206 từ def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)5. Chúng ta có thể khắc phục vấn đề này bằng cách xác định hàm bên trong: def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)5 OUTPUT:Bài kiểm tra sẽ chỉ được thực hiện trong cuộc gọi đầu tiên với def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)5! *Stephen Pinker, The Blate Slate, 2002 Đào tạo Python sống Các khóa học trực tuyến sắp tới Ghi danh ở đây Làm thế nào để bạn trả về một giá trị từ một hàm đệ quy?Với đệ quy, chúng tôi đang chờ các giá trị trả về đến từ các bối cảnh thực thi khác. Những bối cảnh khác cao hơn lên ngăn xếp. Khi mục cuối cùng trên ngăn xếp hoàn thành thực thi, bối cảnh đó sẽ tạo ra giá trị trả về. Giá trị trả về này được truyền xuống dưới dạng giá trị trả về từ trường hợp đệ quy sang mục tiếp theo.When the last item on the stack finishes execution, that context generates a return value. This return value gets passed down as a return value from the recursive case to the next item.
Làm thế nào trả lại hoạt động đệ quy Python?Vâng, khi đệ quy có liên quan, không có gì thay đổi.Câu trả lời không biết và không quan tâm liệu nó có trở lại từ một chức năng được gọi đệ quy hay không, nó hoạt động chính xác theo cùng một cách trong cả hai trường hợp.Trên thực tế, đệ quy không phải là bất cứ điều gì "đặc biệt";Nó hành xử chính xác giống như các cuộc gọi chức năng thông thường.The return statement neither knows nor cares whether it's returning from a recursively invoked function, it behaves exactly the same way in either case. In fact, recursion isn't anything "special" at all; it behaves exactly the same way as ordinary function calls.
Có phải một hàm đệ quy luôn trả về một giá trị?Tất cả các chức năng - đệ quy hay không - có một hoặc nhiều lợi nhuận.Lợi nhuận có thể hoặc không bao gồm một giá trị.Đó là để bạn quyết định khi bạn viết chức năng.The return may or may not include a value. It is for you to decide when you write the function.
Ý nghĩa của sự trở lại trong đệ quy là gì?Một hàm đệ quy trả về một cuộc gọi cho chính nó ở bước I + 1 của quá trình.Để tránh một vòng lặp vô hạn, bạn phải tạo ra SUR, bạn có một điều kiện phá vỡ, dẫn đến sự trở lại với một cái gì đó khác với một cuộc gọi tự.returns a call to itself at the i + 1 step of the process. In order to avoid an infinite loop, you have to make sur you have a break condition, which leads to a return to something different from a self-call. |
