Hướng dẫn how recursion works in python? - cách đệ quy hoạt động trong python?
|
Trong hướng dẫn này, bạn sẽ học cách tạo một hàm đệ quy (một hàm tự gọi). Show
Đệ quy là gì?Đệ quy là quá trình xác định một cái gì đó theo chính nó. Một ví dụ thế giới vật lý sẽ là đặt hai gương song song đối diện nhau. Bất kỳ đối tượng ở giữa chúng sẽ được phản ánh đệ quy. Chức năng đệ quy PythonTrong Python, chúng ta biết rằng một hàm có thể gọi các chức năng khác. Thậm chí có thể cho chức năng gọi chính nó. Các loại cấu trúc này được gọi là các hàm đệ quy. Hình ảnh sau đây cho thấy hoạt động của một hàm đệ quy gọi là  Sau đây là một ví dụ về hàm đệ quy để tìm giai thừa của một số nguyên. Factorial của một số là sản phẩm của tất cả các số nguyên từ 1 đến số đó. Ví dụ: giai thừa của 6 (ký hiệu là 6!) Là 1*2*3*4*5*6 = 720. Ví dụ về hàm đệ quyĐầu ra The factorial of 3 is 6 Trong ví dụ trên, The factorial of 3 is 60 là một hàm đệ quy như nó tự gọi. Khi chúng ta gọi hàm này với số nguyên dương, nó sẽ tự gọi mình bằng cách giảm số. Mỗi hàm nhân số số với giai thừa của số bên dưới nó cho đến khi nó bằng một. Cuộc gọi đệ quy này có thể được giải thích trong các bước sau. factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call Chúng ta hãy xem một hình ảnh hiển thị một quá trình từng bước về những gì đang diễn ra: Đệ quy của chúng tôi kết thúc khi số lượng giảm xuống 1. cái này được gọi là điều kiện cơ sở. Mỗi chức năng đệ quy phải có một điều kiện cơ sở dừng đệ quy hoặc nếu không thì hàm tự gọi chính nó. Thông dịch viên Python giới hạn độ sâu của đệ quy để giúp tránh các đệ quy vô hạn, dẫn đến tràn chồng. Theo mặc định, độ sâu tối đa của đệ quy là 1000. Nếu giới hạn được vượt qua, nó sẽ dẫn đến The factorial of 3 is 61. Hãy nhìn vào một điều kiện như vậy. Đầu ra Traceback (most recent call last): File " Trong ví dụ trên, The factorial of 3 is 60 là một hàm đệ quy như nó tự gọi.
Làm việc của một chức năng giai thừa đệ quy
Xem thảo luận Cải thiện bài viết Lưu bài viết Xem thảo luận Cải thiện bài viết Lưu bài viết Đọc
Tạo trình tự đơn giản hơn thông qua đệ quy hơn là sử dụng bất kỳ lần lặp lồng nhau nào.
Syntax: def func(): <--
|
| (recursive call)
|
func() ----Các chức năng đệ quy là một thách thức để gỡ lỗi. A Fibonacci sequence is the integer sequence of 0, 1, 1, 2, 3, 5, 8…. Python3Lý do đằng sau đệ quy đôi khi có thể khó khăn để suy nghĩ qua. Ví dụ 1: Trình tự Fibonacci là trình tự số nguyên là 0, 1, 1, 2, 3, 5, 8. & NBSP; The factorial of 3 is 62 The factorial of 3 is 63 The factorial of 3 is 64 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call4 The factorial of 3 is 69 The factorial of 3 is 64 The factorial of 3 is 65 The factorial of 3 is 66 The factorial of 3 is 67 The factorial of 3 is 68 The factorial of 3 is 69 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call0 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call1 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call2 Các The factorial of 3 is 64 Traceback (most recent call last): File "6 Traceback (most recent call last): File "7 Traceback (most recent call last): File "8 Traceback (most recent call last): File "9 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call4 The factorial of 3 is 69 The factorial of 3 is 64 Traceback (most recent call last): File "6 Traceback (most recent call last): File "7 def func(): <--
|
| (recursive call)
|
func() ----5Traceback (most recent call last): File "9 The factorial of 3 is 67 Fibonacci series: 0 1 1 2 3 5 8 13 21 342 Traceback (most recent call last): File "6 Fibonacci series: 0 1 1 2 3 5 8 13 21 344
Fibonacci series: 0 1 1 2 3 5 8 13 21 34 Output: Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Python3Đầu ra Ví dụ 2: Factorial của 6 được ký hiệu là 6! = 1*2*3*4*5*6 = 720. & nbsp; The factorial of 3 is 62 The factorial of 3 is 63 The factorial of 3 is 64 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call4 The factorial of 3 is 69 The factorial of 3 is 64 The factorial of 3 is 65 The factorial of 3 is 66 The factorial of 3 is 67 The factorial of 3 is 68 The factorial of 3 is 69 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call0 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call1 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call2 Các The factorial of 3 is 64 Traceback (most recent call last): File "6 Traceback (most recent call last): File "7 recurse8Traceback (most recent call last): File "9 The factorial of 3 is 67 The factorial of 3 is 64 Traceback (most recent call last): File "6 Traceback (most recent call last): File "7 The factorial of 3 is 609 Traceback (most recent call last): File "9 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call4 The factorial of 3 is 69 The factorial of 3 is 65 Traceback (most recent call last): File "1 The factorial of 3 is 67 Traceback (most recent call last): File "3 The factorial of 3 is 69
Factorial of number 6 = 720 def func(): <-- | | (recursive call) | func() ----7 def func(): <-- | | (recursive call) | func() ----8def func(): <-- | | (recursive call) | func() ----9 Fibonacci series: 0 1 1 2 3 5 8 13 21 34 0Fibonacci series: 0 1 1 2 3 5 8 13 21 34 1Đầu raIs it possible to optimize a program by making use of a tail-recursive function instead of non-tail recursive function? Considering the function given below in order to calculate the factorial of n, we can observe that the function looks like a tail-recursive at first but it is a non-tail-recursive function. If we observe closely, we can see that the value returned by Recur_facto(n-1) is used in Recur_facto(n), so the call to Recur_facto(n-1) is not the last thing done by Recur_facto(n). Python3Ví dụ 2: Factorial của 6 được ký hiệu là 6! = 1*2*3*4*5*6 = 720. & nbsp; Fibonacci series: 0 1 1 2 3 5 8 13 21 342 The factorial of 3 is 65 The factorial of 3 is 624 The factorial of 3 is 67 The factorial of 3 is 67 Traceback (most recent call last): File "3 The factorial of 3 is 628 The factorial of 3 is 62 Fibonacci series: 0 1 1 2 3 5 8 13 21 346 The factorial of 3 is 64 The factorial of 3 is 65 Fibonacci series: 0 1 1 2 3 5 8 13 21 349 The factorial of 3 is 67 The factorial of 3 is 67 The factorial of 3 is 68 The factorial of 3 is 69 Traceback (most recent call last): File "6 The factorial of 3 is 641 recurse0Chúng ta có thể viết hàm đã cho recur_facto dưới dạng hàm tái tạo đuôi. Ý tưởng là sử dụng thêm một đối số và trong đối số thứ hai, chúng tôi phù hợp với giá trị của giai thừa. Khi n đạt 0, trả về giá trị cuối cùng của giai thừa của số mong muốn. & Nbsp; Python3The factorial of 3 is 62 The factorial of 3 is 645 The factorial of 3 is 67 The factorial of 3 is 68 The factorial of 3 is 628 Fibonacci series: 0 1 1 2 3 5 8 13 21 342 The factorial of 3 is 65 The factorial of 3 is 624 The factorial of 3 is 67 The factorial of 3 is 67 Traceback (most recent call last): File "3 The factorial of 3 is 628 The factorial of 3 is 629 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call1 The factorial of 3 is 658 Fibonacci series: 0 1 1 2 3 5 8 13 21 342 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call1 The factorial of 3 is 661 factorial(3) # 1st call with 3 3 * factorial(2) # 2nd call with 2 3 * 2 * factorial(1) # 3rd call with 1 3 * 2 * 1 # return from 3rd call as number=1 3 * 2 # return from 2nd call 6 # return from 1st call9 The factorial of 3 is 68 The factorial of 3 is 664 Factorial of number 6 = 7203 The factorial of 3 is 666 Traceback (most recent call last): File "6 The factorial of 3 is 641 recurse0Làm thế nào để đệ quy hoạt động?Một hàm đệ quy giải quyết một vấn đề cụ thể bằng cách gọi một bản sao của chính nó và giải quyết các vấn đề nhỏ hơn của các vấn đề ban đầu.Nhiều cuộc gọi đệ quy hơn có thể được tạo ra khi được yêu cầu.Điều cần thiết là phải biết rằng chúng ta nên cung cấp một trường hợp nhất định để chấm dứt quá trình đệ quy này.. Many more recursive calls can be generated as and when required. It is essential to know that we should provide a certain case in order to terminate this recursion process.
Hàm đệ quy với ví dụ trong Python là gì?Sau đây là một ví dụ về hàm đệ quy để tìm giai thừa của một số nguyên.Factorial của một số là sản phẩm của tất cả các số nguyên từ 1 đến số đó.Ví dụ: giai thừa của 6 (ký hiệu là 6!) Là 1*2*3*4*5*6 = 720.find the factorial of an integer. Factorial of a number is the product of all the integers from 1 to that number. For example, the factorial of 6 (denoted as 6!) is 1*2*3*4*5*6 = 720 . |
