Đệ quy có liên quan đến vô cực. Tôi biết đệ quy có liên quan đến vô cực. Tôi nghĩ rằng tôi biết đệ quy có liên quan đến vô cực. Anh ấy chắc chắn rằng tôi nghĩ rằng tôi biết đệ quy có liên quan gì đó với vô cực. Chúng tôi nghi ngờ anh ấy chắc chắn tôi nghĩ rằng tôi biết Show
Chúng tôi nghĩ rằng, bạn nghĩ, bây giờ chúng tôi đã thuyết phục bạn rằng, chúng ta có thể tiếp tục mãi mãi với ví dụ này về đệ 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 là năng lực nhận thức của con người. Cách suy nghĩ của chúng ta dựa trên quá trình suy nghĩ đệ 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 có chủ ngữ và vị ngữ, và vị ngữ chứa động từ, tân ngữ và bổ ngữ", chúng ta có thể chứng minh khả năng vô tận của ngôn ngữ tự nhiên Nhà khoa học nhận thức và ngôn ngữ học Stephen Pinker diễn đạt nó như thế này. “Với vài nghìn danh từ có thể điền vào ô chủ ngữ và vài nghìn động từ có thể điền vào ô vị ngữ, người ta đã có hàng triệu cách để mở một câu. Các kết hợp có thể 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, kho tàng của các câu về mặt lý thuyết là vô hạn, bởi vì các quy tắc của ngôn ngữ sử dụng một thủ thuật 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ó, như trong Cô ấy nghĩ rằng anh ấy nghĩ rằng họ nghĩ rằng anh ấy biết, v.v., ad infinitum. Và nếu số lượng câu là vô hạn, thì số lượng suy nghĩ và ý định có thể có 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 với việc sử dụng đệ quy trong ngôn ngữ tự nhiên để quay lại với đệ quy trong khoa học máy tính và chương trình và cuối cùng là đệ quy trong ngôn ngữ lập trình Python Tính từ "đệ quy" bắt nguồn từ động từ "recurrere" trong tiếng Latinh, 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 lùi" hoặc trở về chính nó. Hầu hết những người đã làm toán, 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 giai thừa, được định nghĩa theo thuật ngữ toán học là n! = n * (n-1)!, if n > 1 and 0! = 1 Nó thường được sử dụng làm ví dụ cho đệ quy vì tính đơn giản và rõ ràng của nó Đào tạo Python trực tiếp Thưởng thức trang này? Nhìn thấy. Tổng quan về các khóa học Python trực tiếp đăng ký tại đây Định nghĩ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 gọi chính nó một hoặc nhiều lần trong phần thân của nó. Thông thường, nó trả về giá trị trả về của lệnh gọi hàm này. Nếu một định nghĩa hàm thỏa mãn điều kiện đệ quy thì ta gọi hàm này là hàm đệ quy điều kiện chấm dứt. Hàm đệ quy phải đáp ứng một điều kiện quan trọng để được sử dụng trong chương trình. nó phải chấm dứt. Một hàm đệ quy kết thúc, nếu với mỗi lần gọi đệ quy, giải pháp của vấn đề bị thu nhỏ và chuyển sang 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 Ví dụ 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 đề Hàm đệ quy trong PythonBây giờ chúng ta đến để triển khai giai thừa trong Python. Nó dễ dàng và tao nhã 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 thức hoạt động của hàm bằng cách thêm hai hàm print() vào định nghĩa hàm 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)) ĐẦU RAfactorial 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 lại của hàm 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)) ĐẦU RA0 1 1 1 2 2 3 6 4 24 Thực tế phổ biến là mở rộng hàm giai thừa cho 0 làm đối số. Thật hợp lý khi định nghĩ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))1 là 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, bởi vì có chính xác một hoán vị của các đối tượng bằng 0, i. e. nếu không có gì hoán vị, "mọi thứ" được giữ nguyên. Một lý do khác là số cách chọn n phần tử trong n tập hợp được tính bằng n. chia cho tích 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 trực tiếp Thưởng thức trang này? Nhìn thấy. Tổng quan về các khóa học Python trực tiếp Các khóa học trực tuyến sắp tới Khóa học nâng cao chuyên sâu Python dành cho kỹ sư và nhà khoa học đăng ký tại đây Dãy số FibonacciChuyên luận về đệ quy của chúng ta bây giờ dẫn chúng ta đến một trường hợp đệ quy thú vị khác Điểm chung của hoa hướng dương, Tỷ lệ vàng, nón cây linh sam, Mật mã Da Vinci, bài hát "Lateralus" của Tool và hình vẽ bên phải là gì? . Chúng tôi không giới thiệu các số Fibonacci, vì chúng là một ví dụ hữu ích khác cho hàm đệ quy. Cố gắng viết một hàm đệ quy cho dãy số này, có thể dẫn đến một chương trình không hiệu quả. Trên thực tế, không hiệu quả đến mức 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à các số của dãy các giá trị 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$ Dãy Fibonacci được đặt tên theo nhà toán học Leonardo của Pisa, người được biết đến nhiều hơn với tên gọi Fibonacci. Trong cuốn sách "Liber Abaci" (xuất bản năm 1202), ông đã giới thiệu trình tự này như một bài tập đối phó với những chú thỏ. Dãy số Fibonacci của ông bắt đầu bằng F1 = 1, trong khi trong toán học hiện đại, dãy số 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ố cặp thỏ sau 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 tháng, tôi. e. sau 10 tháng chúng ta sẽ có $F_10$ thỏ Các số Fibonacci rất dễ viết dưới dạng hàm Python. Nó ít nhiều là ánh xạ 1-1 từ định nghĩa toán học def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) Một giải pháp lặp lại cũng dễ viết, mặc dù giải pháp đệ quy trông giống định nghĩa hơn 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 10 Chúng tôi sẽ viết một mô-đun có tê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))4 chứa cả chức năng 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 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))6. Để làm điều này, bạn phải sao chép đoạn mã sau vào một tệp có tên fibonacci0. py 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 11 ĐẦU RA4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 12 Nếu bạn kiểm tra các hàm fib() và fibi(), bạn sẽ thấy rằng phiên bản lặp fibi() nhanh hơn rất nhiều so với phiên bản đệ quy fib(). Để biết được mức độ "nhanh hơn rất nhiều" này có thể là bao nhiêu, chúng tôi đã viết một tập lệnh sử dụng mô-đun timeit để đo các cuộc gọi. Để làm điều này, chúng tôi lưu các định nghĩa hàm cho fib và fibi trong tệp fibonacci. py, mà chúng ta có thể nhập vào chương trình (fibonacci_runit. py) bên dưới 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 13 ĐẦU RA4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 14 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 là thời gian tính bằng giây để 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))8 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))9 tương ứng là thời gian cho 0 1 1 1 2 2 3 6 4 240 Có gì sai với việc triển khai đệ quy của chúng tôi? Hãy nhìn vào cây tính toán, tôi. e. thứ tự mà các chức năng được gọi. fib() được thay thế bằng f() Ta thấy cây con f(2) xuất hiện 3 lần và cây con để tính f(3) xuất hiện 2 lần. Nếu bạn tưởng tượng mở rộng cây này cho f(6), bạn sẽ hiểu rằng f(4) sẽ được gọi 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ị đã tính toán trước đó. Chúng tôi gọi đây là phiên bản 0 1 1 1 2 2 3 6 4 241 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 15 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 sẽ thêm nó vào mô-đun 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ủa chúng tôi 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 16 ĐẦU RA4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 17 Chúng tôi hẹn giờ lại để so sánh nó với fibi() 4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 18 ĐẦU RA4! = 4 * 3! 3! = 3 * 2! 2! = 2 * 19 Chúng ta có thể thấy rằng nó thậm chí còn nhanh hơn phiên bản lặp lại. Tất nhiên, các đối số càng lớn, lợi ích của việc ghi nhớ của chúng ta càng lớn. Chúng ta cũng có thể định nghĩa một thuật toán đệ quy cho hàm Fibonacci của mình bằng cách sử dụng một lớp có thể hiện callabe, i. e. bằng cách sử dụng cuộc gọi phương thức đặc biệt. Bằng cách này, chúng tôi sẽ có thể ẩn 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 as xác định các hàm 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 thể hiện của lớp này. Về cơ bản, nguyên tắc xây dựng, tôi. e. tổng của hai số liền trước sẽ bằng nhau. Chúng sẽ khác nhau bởi hai giá trị ban đầu 4! = 4 * 3 * 2 * 10 ĐẦU RA4! = 4 * 3 * 2 * 11 Số Lucas hay chuỗi Lucas là một dãy số nguyên được đặt theo tên của nhà toán học François Édouard Anatole Lucas (1842–91), người đã nghiên cứu cả dãy số đó 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, i. e. tổng của hai số liền trước nhưng giá trị của 0 và 1 khác nhau Dãy Fibonacci Tổng quátBây giờ chúng tôi sẽ chứng minh rằng phương pháp 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 ý. Dãy Fibonacci phụ thuộc vào hai giá trị đứng trước. Bây giờ chúng tôi khái quát hóa khái niệm này bằng cách xác định chuỗi k-Fib theo cách sau Cho một số tự nhiên cố định 0 1 1 1 2 2 3 6 4 243 và 0 1 1 1 2 2 3 6 4 244. Cũng được cung cấp 0 1 1 1 2 2 3 6 4 243 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}$ Hàm này cũng cần các hệ số $k$ $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$ 4! = 4 * 3 * 2 * 12 ĐẦU RA4! = 4 * 3 * 2 * 11 Dãy số Pell bắt đầu bằng 1, 2, 5, 12, 29, chức năng 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 trình tự này với lớp 0 1 1 1 2 2 3 6 4 246 của chúng tôi 4! = 4 * 3 * 2 * 14 ĐẦU RA4! = 4 * 3 * 2 * 15 Chúng ta có thể tạo ra một chuỗi thú vị khác bằng cách cộng tổng của hai số Pell trước đó vào 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) tương ứng với. $1, 2, 3, 5, 7, 12, 17, 29, \ldots $ 4! = 4 * 3 * 2 * 16 ĐẦU RA4! = 4 * 3 * 2 * 17 Nếu bạn nhìn kỹ vào các con số, bạn có thể thấy rằng có một quy luật khác trong dãy số này. Chúng ta có thể định nghĩa nP là $nP(n) = 2 \cdot nP(n-2) + nP(n-4)$ với $n > 3$ và các giá trị bắt đầu $1, 2, 3, 5$ Đây là một ứng dụng dễ dàng khác cho lớp 0 1 1 1 2 2 3 6 4 246 của chúng tôi 4! = 4 * 3 * 2 * 18 ĐẦU RA4! = 4 * 3 * 2 * 17 Một thực tế toán học thú vị. Với mọi n lẻ, thương của $P(n)$ với $P(n-1)$ là một xấp xỉ của $\sqrt{2}$. Nếu 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 chẵn, thương số sẽ xấp xỉ bằng $1 + {1 \over {\sqrt{2}}}$ def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)0 ĐẦU RAdef factorial(n): if n == 0: return 1 else: return n * factorial(n-1)1 Đào tạo Python trực tiếp Thưởng thức trang này? Nhìn thấy. Tổng quan về các khóa học Python trực tiếp đăng ký tại đây 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 thử giải các bài tập sau. Xin đừ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 đã suy nghĩ về một nhiệm vụ trong một thời gian mà bạn vẫn không có khả năng giải bài tập, bạn có thể tham khảo các bài giải mẫu của chúng tôi Trong phần "Chủ đề nâng cao" của phần hướng dẫn, chúng tôi có 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 hàm sử dụng hàm đệ quy. “Bài toán Hà Nội” rất đặc biệt, bởi lời giải đệ quy gần như bó buộc người lập trình, trong khi lời giải 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, i. e. bội số của 3 Bài tập 2Viết hàm Python đệ quy trả về tổng của n số nguyên đầu tiên. (Gợi ý. Chức năng sẽ tương tự như chức năng giai thừa. ) bài tập 3Viết hàm thực hiện tam giác Pascal def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)2 bài tập 4Dãy số Fibonacci ẩn bên trong tam giác Pascal. Nếu cộng các số đã tô màu của tam giác sau, bạn sẽ được số Fibonacci thứ 7 def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)3 Viết chương trình đệ quy tính dãy số Fibonacci sử dụng tam giác Pascal bài tập 5Triển khai hàm đệ quy trong Python cho sàng của Eratosthenes Sàng của Eratosthenes là một thuật toán đơn giản để tìm tất cả các số nguyên tố cho đến một số nguyên xác định. Nó được tạo ra bởi 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 một số nguyên n cho trước
Bạn có thể dễ dàng thấy rằng chúng ta sẽ kém hiệu quả nếu sử dụng thuật toán này một cách nghiêm ngặt, e. g. chúng tôi sẽ cố gắng loại bỏ bội số của 4, mặc dù chúng đã bị loại bỏ 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ể đệ quy tạo các bộ này bài tập 6Viết hàm đệ quy fib_indexfib(), hàm này trả về chỉ số của một số trong dãy Fibonacci, nếu số đó là một phần tử của dãy này và trả về -1 nếu không chứa số đó, i. e $fib(fib\_index(n)) == n$ bài tập 7Tổng bình phương của hai số Fibonacci liên tiếp cũng là một số Fibonacci, e. g. 2 và 3 là các phần tử của dãy Fibonacci và 22 + 33 = 13 tương ứng với Fib(7). Sử dụng hàm trước để tìm vị trí tổng bình phương của hai số liên tiếp trong dãy Fibonacci giải thích toán học. Cho a và b là hai số Fibonacci liên tiếp với a đứng trước b. Dãy Fibonacci bắt đầu bằng số "a" trông như thế này def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)4 Chúng ta có thể thấy rằng các số Fibonacci xuất hiện dưới dạng thừa số cho a và b. Phần tử thứ n trong dãy này có thể được tính bằng công thức sau $F(n) = Fib(n-1) \cdot a + Fib(n) \cdot b$ Từ đó ta có thể kết luận rằng với số tự nhiên n, n>1, đ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 bằng hai số hạng được xác định trước, dãy số bắt đầu bằng ba số hạng được xác định trước và mỗi số hạng sau đó là tổng của ba số hạng trước đó. Một vài số tribonacci đầu tiên là def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)5 Các số tetranacci bắt đầu bằng bốn số hạng được xác định trước, mỗi số hạng sau là tổng của bốn số hạng trước đó. Một vài số tetranacci đầu tiên là def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)6 Điều này tiếp tục theo cách tương tự đối với pentanacci, hexanacci, heptanacci, octanacci, v.v. Viết một hàm 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 hàm đệ quy? . Được rồi, hãy viết một phiên bản đệ quy của giai thừa, để kiểm tra các tham số. Có thể bạn đã làm nó một cách hoàn hảo, nhưng có thể không. Bạn có thể cải thiện phiên bản của bạn? Đào tạo Python trực tiếp Thưởng thức trang này? Nhìn thấy. Tổng quan về các khóa học Python trực tiếp đăng ký tại đây Các giải phápGiải 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 def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)7 ĐẦU RAdef factorial(n): if n == 0: return 1 else: return n * factorial(n-1)8 Giải bài tập 2def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)9 Giải bài tập 3. Tạo tam giác Pascaldef 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 ĐẦU RAdef 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 Ngoài ra, chúng ta có thể viết một hàm bằng cách sử dụng khả năng hiểu danh sá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))2 ĐẦU RAdef 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 Giải bài tập 4Tạo các số Fibonacci từ tam giác Pascal 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 ĐẦU RAdef 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))5 Lời giải bài tập 5Chương trình sau 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 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))6 ĐẦU RAdef 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))7 Nhưng chương này của hướng dẫn của chúng tôi là về đệ quy và các hàm đệ quy, và chúng tôi đã yêu cầu một hàm đệ quy để tính các số nguyên tố. Để hiểu giải pháp sau đây, bạn có thể tham khảo chương của chúng tôi về Hiểu danh sá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))8 ĐẦU RAdef 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))7 Lời giải bài tập 6factorial 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 ĐẦU RAfactorial 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 1201 Lời giải bài tập 8Chúng ta sẽ sử dụng lớp 0 1 1 1 2 2 3 6 4 246 mà chúng ta đã định nghĩa trong chương này 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 ĐẦU RAfactorial 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 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 1204 ĐẦU RAfactorial 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 Chúng ta có thể dễ dàng tạo chúng như thế này 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 ĐẦU RAfactorial 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 Giải bài tập 9factorial 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 Bạn nghĩ gì về giải pháp này? . Hàm sẽ kiểm tra xem def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)1 có phải là số nguyên dương không. Hàm sẽ gọi đệ quy def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)2. Trong lần gọi này, hàm sẽ kiểm tra lại, nếu def factorial(n): if n == 0: return 1 else: return n * factorial(n-1)3 là số nguyên. nó có thể là gì khác? Ví dụ hàm đệ quy là gì?Một ví dụ kinh điển về đệ quy
. Giai thừa của một số được tính khi số đó nhân với tất cả các số bên dưới nó cho đến và bằng 1. Ví dụ: giai thừa(5) giống như 5*4*3*2*1 và giai thừa(3) là 3*2*1. computing factorials. The factorial of a number is computed as that number times all of the numbers below it up to and including 1. For example, factorial(5) is the same as 5*4*3*2*1 , and factorial(3) is 3*2*1 .
Hàm đệ quy nghĩa là gì?Hàm đệ quy là hàm lặp lại hoặc sử dụng số hạng trước đó của chính nó để tính các số hạng tiếp theo và do đó tạo thành một chuỗi các số hạng . Thông thường, chúng ta tìm hiểu về hàm số này dựa trên dãy số-hình học, trong đó có các hạng tử có sự khác biệt chung giữa chúng. |
