programming python

Python có đệ quy đuôi không?

Khái niệm đệ quy, theo định nghĩa đơn giản nhất là một hàm gọi chính nó, được áp dụng rộng rãi trong không gian lập trình vì nó giúp chia nhỏ các bài toán phức tạp lớn hơn thành các bài toán con nhỏ hơn, có thể giải quyết dễ dàng hơn và các câu trả lời của chúng có thể được kết hợp với nhau . Một trong những ví dụ thường thấy nhất cho hàm đệ quy là tính giai thừa của một số

Bạn sẽ viết hàm như vậy bằng Python như thế nào?

Đây là một lời gọi đệ quy và nếu chúng ta xem kỹ cách máy tính xử lý đệ quy chi tiết hơn, chúng ta biết rằng với mỗi lời gọi đệ quy, một ngăn xếp sẽ được tạo và đẩy vào bộ nhớ. Ngăn xếp này chứa tất cả thông tin thích hợp bao gồm các giá trị tham số cho hàm. Khi chức năng kết thúc [i. e. trường hợp cơ sở được gọi], thông tin được bật ra khỏi ngăn xếp và mỗi giá trị trong lệnh gọi được trả về và cuối cùng là giá trị cuối cùng được trả về, như được minh họa trong sơ đồ này

nguồn. https. //www. đám mâyavvyit. com/11720/đệ-quy-trong-lập-trình-và-bạn-dùng-nó-như-thế-nào/

Có một chút phức tạp liên quan ở đây vì bộ nhớ của chúng tôi bị hạn chế - chúng tôi không có tài nguyên vô hạn, vì vậy nếu chúng tôi kích hoạt một số lượng lớn các lệnh gọi đệ quy, độ sâu ngăn xếp sẽ trở nên rất lớn và chúng tôi có thể đạt đến mức tối đa của không gian ngăn xếp. Ví dụ: chúng ta sẽ gặp 

120
67 trong Python khi cố gắng tìm giai thừa của 10000 bằng hàm chúng ta vừa tạo

Có cách nào để tối ưu hóa nó nếu chúng ta vẫn muốn sử dụng đệ quy? . Một hàm là đệ quy đuôi nếu nó kết thúc bằng cách trả về giá trị của lệnh gọi đệ quy — trong khi nếu bất kỳ quá trình xử lý nào khác được thực hiện trên giá trị trả về của lệnh gọi đệ quy thì hàm đó không phải là đệ quy đuôi. Ví dụ, trong trường hợp của chúng tôi, giá trị của 

120
68 được sử dụng để nhân với 
120
69. Máy tính rất thông minh và nếu chúng biết chúng ta sẽ không làm gì khác với giá trị trả về, chúng sẽ không thêm ngăn xếp khác và sử dụng lại ngăn xếp hiện có. Như vậy về lý thuyết ta sẽ không gặp lỗi của 
120
67 khi tối ưu đệ quy đuôi

Ok, vậy làm cách nào để chúng tôi sửa đổi chức năng của mình để tối ưu hóa đệ quy đuôi?

Chức năng này có thể chính xác như những gì chúng ta muốn — ngoại trừ việc nó không hoạt động. [

Mặc dù một số ngôn ngữ lập trình tự động nhận dạng và tối ưu hóa chức năng đệ quy đuôi, nhưng Python là ngôn ngữ thích có truy nguyên thích hợp. Người tạo ra ngôn ngữ Python, Guido van Rossum cũng đã đề cập trong hai blog của mình [liên kết & liên kết] về việc ông không thích tối ưu hóa đệ quy đuôi như thế nào. Anh ấy tin rằng việc bật tối ưu hóa đệ quy đuôi có thể gây nhầm lẫn cho những người dùng vô tình viết nội dung đệ quy nào đó và cần gỡ lỗi. Đó cũng là niềm tin cơ bản khác nhau của các nhà khoa học máy tính khác nhau. Tôi sẽ không bình luận về các ý kiến ​​ở đây, nhưng tôi tin rằng chúng ta nên luôn được khuyến khích nghĩ đến việc tối ưu hóa các chức năng của mình, thay vì chỉ bắt chúng hoạt động, vì vậy tôi đã thực hiện một số nghiên cứu về một số cách chúng ta có thể thực hiện 'một cách' chiến thuật đuôi

Đầu tiên, chúng ta có thể tạo một decorator [về khái niệm decorator trong Python, vui lòng đọc tại đây. ] để chức năng của chúng tôi làm cho cuộc gọi đuôi được tối ưu hóa

Một cách khác để tránh lỗi

120
67là sử dụng hàm lặp thay vì hàm đệ quy

Đệ quy đuôi được định nghĩa là một hàm đệ quy trong đó lời gọi đệ quy là câu lệnh cuối cùng được thực hiện bởi hàm. Vì vậy, về cơ bản không còn gì để thực thi sau lệnh gọi đệ quy

Ví dụ hàm C++ print[] sau đây là đệ quy đuôi

C




120
72

 

120
73 
120
74
120
75 
120
76

120
77

120
78
120
79 
120
0

_______01____02____03

120
78
120
5
120
6 
120
7

 

120
78
120
9

120
78
120
721

120
722

C++




120
72

 

120
724 
120
73 
120
74
120
75 
120
76

120
77

120
78
120
79 
120
0

_______01____02____03

120
78
120
5
120
6 
120
7

120
740

120
78
120
9

120
78
120
721

120
722

 

120
746

Java




120
72

 

120
724 
120
73 
120
74
120
75 
120
76

120
77

120
78
120
79 
120
756______1757
120
758

_______01____02____03

 

120
78
120
763____06 
120
765

 

120
78
120
767

120
78
120
769

120
78
120
771____1772
120
773

120
722

 

120
775

Python3




120
776

 

 

________ 1777 ________ 1778

 

120
78
120
79 
120
756______1757
120
783

120
1
120
2

120
78
120
787
120
788
120
789
120
790
120
791
120
792
120
758

 

120
78
120
795

120
78
120
797____1798
120
772
120
758

 

120
78
120
02

120
78
120
04

C#




120
72

 

120
724 
120
73 
120
74
120
75 
120
76

120
77

120
78
120
79 
120
0

_______01____02____03

 

120
78
120
19
120
6 
120
765

 

120
78
120
767

120
78
120
769

120
78
120
721

120
722

 

120
29

Javascript




120
30

120
72

120
32 
120
33

120
77

120
78
120
79 
120
0

_______038____02____03

120
41

120
78
120
43____06 
120
765

120
41

120
78
120
767

120
38
120
769

120
78
120
721

120
722

 

120
54

120
55

Cần đệ quy đuôi

Các hàm đệ quy đuôi được coi là tốt hơn các hàm đệ quy không đuôi vì trình biên dịch có thể tối ưu hóa đệ quy đuôi.  

Trình biên dịch thường thực hiện các thủ tục đệ quy bằng cách sử dụng ngăn xếp. Ngăn xếp này bao gồm tất cả các thông tin thích hợp, bao gồm các giá trị tham số, cho mỗi lệnh gọi đệ quy. Khi một thủ tục được gọi, thông tin của nó được đẩy vào ngăn xếp và khi chức năng kết thúc, thông tin sẽ được đưa ra khỏi ngăn xếp. Do đó, đối với các hàm không đệ quy đuôi, độ sâu ngăn xếp [lượng không gian ngăn xếp tối đa được sử dụng bất kỳ lúc nào trong quá trình biên dịch] là nhiều hơn.  

Ý tưởng được các trình biên dịch sử dụng để tối ưu hóa các hàm đệ quy đuôi rất đơn giản, vì lời gọi đệ quy là câu lệnh cuối cùng, không còn gì để làm trong hàm hiện tại, vì vậy việc lưu khung ngăn xếp của hàm hiện tại là vô ích [Xem phần này để biết thêm

Hàm không đệ quy đuôi có thể được viết dưới dạng đệ quy đuôi để tối ưu hóa nó không?

Xét hàm sau để tính giai thừa của n.  

Nó là một hàm không đệ quy đuôi. Mặc dù thoạt nhìn nó giống như một đệ quy đuôi. Nếu chúng ta xem xét kỹ hơn, chúng ta có thể thấy rằng giá trị được trả về bởi fact[n-1] được sử dụng trong fact[n]. Vì vậy, lời gọi đến fact[n-1] không phải là điều cuối cùng được thực hiện bởi fact[n]

C++




120
56

120
57 
120
58 
120
59

 

120
60

120
61

120
62

120
63

120
64
120
75 
120
66
120
75 
120
76

120
77

120
78
120
79 
120
72

120
1
120
2 
120
75

 

120
78
120
2 
120
78

120
722

 

120
80

120
75 
120
82

120
77

120
78
120
85

120
78
120
2 
120
88

120
722

Java




120
90 
120
91

 

120
78
120
93

120
78
120
95

120
78
120
97

120
78
120
99

120
78
120
7201

120
78____17203

120
78____17205

120
78
120
724 
120
75 
120
7209
120
75 
120
76

120
78
120
77

120
1
120
79 
120
7216
120
757
120
758

120
7219
120
2 
120
772
120
3

 

120
1
120
2 
120
7225____1772
120
773

120
78
120
722

 

120
78____17231

120
78
120
7233 
120
724 
120
73 
120
7236

120
78
120
77

120
1____17240
120
7241
120
7242

120
78
120
722

120
722

 

120
7246

Python3




120
7247

120
7248

120
7249

120
7250

120
7251

120
7252

120
7253

 

 

120
777 
120
7255

120
78
120
79 
120
7258
120
791
120
791 
120
757
120
783

120
1
120
2 
120
772

120
78
120
2 
120
7268
120
7269 
120
7270
120
798
120
772
120
758

 

 

120
7274

120
7275

120
79 
120
7277
120
791
120
791 
120
7280
120
7281

120
78
120
787
120
7284
120
7241
120
7286

 

120
7287

C#




120
57 
120
7289

 

120
90 
120
91

 

120
78
120
93

120
78
120
95

120
78
120
97

120
78
120
99

120
78
120
7201

120
78____17203

120
78____17205

120
78
120
724 
120
75 
120
7209
120
75 
120
76

120
78
120
77

120
1
120
79 
120
7316

120
7219
120
2 
120
75

 

120
1
120
2 
120
78

120
78
120
722

 

120
78____17326

120
78____17328

120
78
120
7233 
120
724 
120
73 
120
7333

120
722

 

120
7335

PHP




120
7336

120
93

120
95

120
97

120
7340

120
7341

120
7342

 

120
32 
120
7209
120
7345
120
758

120
77

120
78
120
79 
120
788
120
7345 
120
7352
120
2 
120
75

 

120
78
120
2 
120
7345 
120
7358
120
7345 
120
7360

120
722

 

120
78
120
7363

120
78
120
7365 
120
7366

 

120
7367

120
7368

Javascript




120
30

 

120
93

120
95

120
97

120
99

120
7201

120
7203

120
7205

120
32 
120
7378

120
77

120
78
120
79 
120
7316

120
1
120
2 
120
75

120
740

120
78
120
2 
120
78

120
722

 

120
7391

120
7392

 

120
29

 

120
55

Đầu ra

120

Hàm trên có thể được viết dưới dạng hàm đệ quy đuôi. Ý tưởng là sử dụng thêm một đối số và tích lũy giá trị giai thừa trong đối số thứ hai. Khi n về 0, trả về giá trị tích lũy

Dưới đây là cách triển khai sử dụng hàm đệ quy đuôi

C++




120
56

120
57 
120
58 
120
59

 

120
7399

120
7400
120
75 
120
7402
120
75 
120
7404

120
77

120
78
120
79 
120
7408

120
1
120
2 
120
7411

 

120
78
120
2 
120
7414

120
722

 

120
7416

120
64______175 
120
66
120
75 
120
7421
120
2 
120
7423

 

120
80

120
75 
120
82

120
77

120
78
120
85

120
78
120
2 
120
88

120
722

Java




120
7434

 

120
90 
120
91

 

120
78____17438

120
78
120
7440

120
78
120
724 
120
75 
120
7444
120
75 
120
7446
120
75 
120
7404

120
78
120
77

120
1
120
79 
120
7453____1757
120
758

120
7219
120
2 
120
7411

 

120
1
120
2 
120
7461
120
772
120
7463

120
78
120
722

 

120
78
120
7416

120
78
120
724 
120
75 
120
7209
120
75 
120
7421
120
2 
120
7475
120
772
120
7477

 

120
78
120
7391

120
78
120
724 
120
7233 
120
73 
120
7236

120
78
120
77

120
1____17240
120
7241
120
7242

120
78
120
722

120
722

 

120
7246

Python3




120
7495

120
7496

 

 

120
777 
120
7498
120
791
120
772
120
783

 

120
78
120
79 
120
756______1791 
120
772
120
783

120
1
120
2 
120
7510

 

120
78
120
2 
120
7270
120
798 
120
772
120
7516
120
7269 
120
7404

 

 

120
7274

120
7275

120
787
120
7284
120
7241
120
7286

 

120
7525

120
7526

120
7527

C#




120
7528

 

120
57 
120
7289

 

120
90 
120
91

 

120
78____17438

120
78
120
7440

120
78
120
724 
120
75 
120
7444
120
75 
120
7446
120
75 
120
7404

120
78
120
77

120
1
120
79 
120
72

120
7219
120
2 
120
7411

 

120
1
120
2 
120
7414

120
78
120
722

 

120
78
120
7416

120
78
120
724 
120
75 
120
7209
120
75 
120
7421
120
2 
120
7423

 

120
78
120
7391

120
78
120
724 
120
7233 
120
73 
120
7574

120
78
120
77

_______01____17578

120
78
120
722

120
722

 

120
7582

PHP




120
7336

 

120
7438

120
7440

120
32 
120
7444
120
7345
120
7589
120
7590
120
758

120
77

120
78
120
79 
120
788
120
7345 
120
7597
120
2 
120
7590
120
3

 

120
78
120
2 
120
7444
120
7345 
120
7605
120
7345 
120
7269
120
7590
120
773

120
722

 

120
7416

120
32 
120
7209
120
7345
120
758

120
77

120
78
120
2 
120
7444
120
7345
120
7621

120
722

 

120
7326

120
7328

120
7365 
120
7366

 

120
7627

120
7628

120
7368

Javascript




120
30

 

120
7631

 

120
7438

120
7440

120
32 
120
7635

120
77

120
78
120
79 
120
72

120
1
120
2 
120
7411

120
740

120
78
120
2 
120
7414

120
722

120
740

120
7416

120
32 
120
7378

120
77

120
78
120
2 
120
7655

120
722

 

120
7391

120
7392

 

120
7659

120
78

120
55

Đầu ra

120

Các bài viết tiếp theo về chủ đề này.  

  • Loại bỏ cuộc gọi đuôi
  • QuickSort Tail Call Optimization [Giảm khoảng trống trong trường hợp xấu nhất thành Log n ]

Vui lòng viết bình luận nếu bạn thấy bất cứ điều gì không chính xác hoặc bạn muốn chia sẻ thêm thông tin về chủ đề thảo luận ở trên

Ngôn ngữ nào có đệ quy đuôi?

Loại bỏ đệ quy đuôi là một tính năng rất thú vị có sẵn trong các ngôn ngữ Lập trình hàm, như Haskell và Scala . Nó thực hiện các cuộc gọi hàm đệ quy nhanh như vòng lặp.

Đệ quy đuôi có nhanh hơn trong Python không?

Nó sử dụng ít bộ nhớ hơn so với hàm đệ quy không đuôi. Nhanh hơn vì trình biên dịch có thể thực hiện tối ưu hóa đặc biệt cho các lệnh gọi hàm đệ quy đuôi .

Có đệ quy trong Python không?

Python cũng chấp nhận đệ quy hàm , nghĩa là một hàm đã xác định có thể gọi chính nó. Đệ quy là một khái niệm toán học và lập trình phổ biến. Nó có nghĩa là một chức năng gọi chính nó.

Python có ngăn xếp cuộc gọi không?

Trình thông dịch Python sử dụng ngăn xếp lệnh gọi để chạy chương trình Python . Khi một hàm được gọi trong Python, một khung mới được đẩy lên ngăn xếp cuộc gọi để thực thi cục bộ của nó và mỗi khi lệnh gọi hàm trả về, khung của nó sẽ bị bật ra khỏi ngăn xếp cuộc gọi.

Bài Viết Liên Quan

Làm cách nào để tạo một phòng chat trong python?
Câu hỏi phỏng vấn html css và javascript là gì?
Làm cách nào để thay đổi màu động trong JavaScript?
Làm cách nào để bạn lưu trữ nhiều đầu vào từ vòng lặp for trong python?
Cách nhập ngày trong PHP
Football Manager 2023 beta có miễn phí không?
Linux cài đặt phần mở rộng php
Làm cách nào để xóa dấu phẩy và dấu ngoặc trong python?
Cách chuyển tuple làm đối số trong python
Socket Python geeksforgeeks
When can I enter the 2024 Diversity visa program?
Python lấy tất cả các thuộc tính và giá trị của đối tượng
Làm cách nào để xóa nhiều khoảng trắng khỏi chuỗi trong PHP?
Print_r được sử dụng để làm gì trong PHP?
Where is the British Open in 2024?
Làm cách nào để căn chỉnh văn bản để in trong excel?
Liên kết ngoài trong WordPress là gì?
Toyota Yaris Cross 2023 Úc
Văn bản bao bọc trong bảng Python
Hình tròn CSS

Toplist mới

#1
Top 6 bản thân em phải làm gì để phòng chống hiv/aids 2023
7 tháng trước
#2
Top 7 số 20 gồm 2 và 0 đúng hay sai 2023
7 tháng trước
#3
Top 7 địa lý lớp 6 bài 19: lớp đất và các nhân tố hình thành đất một số nhóm đất điển hình trang 178 2023
7 tháng trước
#4
Top 7 h thực hiện chủ trương đường lối chính sách của đảng pháp luật của nhà nước 2023
7 tháng trước
#5
Top 6 on tập tiếng việt lớp 7 học kĩ 2 violet 2023
7 tháng trước
#6
Top 7 trung du và miền núi bắc bộ có thế mạnh nổi bật về luyện kim đen 2023
7 tháng trước
#7
Top 8 mơ thấy có người to tình với mình 2023
7 tháng trước
#8
Top 6 nước yến cao cấp yến sào thiên hoàng 2023
7 tháng trước
#9
Top 7 ví dụ về quyết định hành chính nhà nước 2023
7 tháng trước

Bài mới nhất

Lỗi không thể tạo quảng cáo trên facebook năm 2024
Bài tập so sánh lũy thừa lớp 6 năm 2024
Đề thi chứng chỉ hành nghề kế toán năm 2024
Chế hóa ngồi quay lưng ra cửa đi năm 2024
Toán lớp 5 bài luyện tập chung trang 175 năm 2024
Bị lỗi new feed fb trên máy tính năm 2024
Lỗi scanning and repairing drive system partition c win 10 năm 2024
Bài tập thì bị động tương lai đơn violet.vn năm 2024
Tuổi đinh mão 1987 xuất hành hướng nào năm 2024
Top sao nam quyen ru nhat han quoc năm 2024

Chủ Đề

Hỏi Đáp Mẹo Hay Toplist Là gì Địa Điểm Hay programming mẹo hay Học Tốt Công Nghệ Nghĩa của từ Khỏe Đẹp Bao nhiêu đánh giá Top List bao nhieu bao nhiêu hướng dẫn Bài tập So Sánh Tiếng anh So sánh Xây Đựng Sản phẩm tốt Ngôn ngữ Món Ngon Bài Tập Thế nào Ở đâu Tại sao Hướng dẫn Máy tính Dịch Đại học Bao lâu Khoa Học Vì sao