Bạn có thể muốn chia một vấn đề phức tạp thành nhiều vấn đề nhỏ hơn. Bạn đã quen thuộc với các vòng lặp hoặc phép lặp. Trong một số trường hợp đệ quy có thể là một giải pháp tốt hơn
Trong Python, một hàm là đệ quy nếu nó gọi chính nó và có điều kiện kết thúc. Tại sao một điều kiện chấm dứt?
Khóa học liên quan
Bootcamp lập trình Python. Đi từ số không đến anh hùng
ví dụ đệ quy
Đệ quy với một danh sách
Hãy bắt đầu với một ví dụ rất cơ bản. thêm tất cả các số trong một danh sách. Nếu không có đệ quy, đây có thể là.
#!/usr/bin/env python
def sum[list]:
sum = 0
# Add every number in the list.
for i in range[0, len[list]]:
sum = sum + list[i]
# Return the sum.
return sum
print[sum[[5,7,3,8,10]]]
Khi chúng ta chỉ đơn giản gọi hàm tổng, hàm sẽ thêm mọi phần tử vào biến tổng và trả về. Để làm điều này đệ quy
#!/usr/bin/env python
def sum[list]:
if len[list] == 1:
return list[0]
else:
return list[0] + sum[list[1:]]
print[sum[[5,7,3,8,10]]]
Nếu độ dài của danh sách là một thì nó trả về danh sách [điều kiện kết thúc]. Ngược lại, nó trả về phần tử và gọi hàm sum[] trừ đi một phần tử của danh sách. Nếu tất cả các cuộc gọi được thực hiện, nó sẽ trả về điều kiện kết thúc và trả về câu trả lời
Giai thừa với đệ quy
Định nghĩa toán học của giai thừa là. N. = n * [n-1]. , nếu n > 1 và f[1] = 1. Thí dụ. 3. = 3 x 2 x 1 = 6. Chúng ta có thể thực hiện điều này trong Python bằng hàm đệ quy
#!/usr/bin/env python
def factorial[n]:
if n == 1:
return 1
else:
return n * factorial[n-1]
print[factorial[3]]
Khi gọi hàm giai thừa n = 3. Do đó, nó trả về n * giai thừa [n-1]. Quá trình này sẽ tiếp tục cho đến khi n = 1. Nếu đạt n==1 sẽ trả về kết quả
Hạn chế của đệ quy
Mỗi khi một chức năng gọi chính nó và lưu trữ một số bộ nhớ. Do đó, một hàm đệ quy có thể chứa nhiều bộ nhớ hơn một hàm truyền thống. Python dừng các cuộc gọi chức năng sau độ sâu 1000 cuộc gọi. Nếu bạn chạy ví dụ này.
#!/usr/bin/env python
def factorial[n]:
if n == 1:
return 1
else:
return n * factorial[n-1]
print[factorial[3000]]
Bạn sẽ nhận được lỗi
RuntimeError: maximum recursion depth exceeded
Trong các ngôn ngữ lập trình khác, chương trình của bạn có thể bị sập. Bạn có thể giải quyết vấn đề này bằng cách sửa đổi số lần gọi đệ quy, chẳng hạn như
#!/usr/bin/env python
import sys
sys.setrecursionlimit[5000]
def factorial[n]:
if n == 1:
return 1
else:
return n * factorial[n-1]
print[factorial[3000]]
nhưng hãy nhớ rằng vẫn có giới hạn đối với đầu vào cho hàm giai thừa. Vì lý do này, bạn nên sử dụng đệ quy một cách khôn ngoan. Như bạn đã học bây giờ đối với bài toán giai thừa, hàm đệ quy không phải là giải pháp tốt nhất. Đối với các vấn đề khác như duyệt qua một thư mục, đệ quy có thể là một giải pháp tốt
Khóa học liên quan
Bootcamp lập trình Python. Đi từ số không đến anh hùng
Quay lạiTiếp theo
Đăng trong người mới bắt đầu
2015-09-03
- con trăn
- đệ quy
Để lại một câu trả lời
Đừng điền vào đây nếu bạn là con người.
Tên
Địa chỉ emailThông điệp
Gửi tin nhắn
Hại • Thứ Hai, ngày 15 tháng 6 năm 2015
Cảm ơn về Hướng dẫn
Frank • Thứ ba, ngày 16 tháng 6 năm 2015
cảm ơn hại. Sắp có thêm hướng dẫn
Aj • Thứ ba, ngày 23 tháng 6 năm 2015
Đó là một con số lớn. o,
Cảm ơn các Hướng dẫn bạn đã giúp tôi rất nhiều
Frank • Thứ Ba, ngày 23 tháng 6 năm 2015
Thanks. Sắp có thêm hướng dẫn
John Youn • Thứ Tư, ngày 24 tháng 6 năm 2015
Cảm ơn rất nhiều. Tôi đang mong đợi nhiều hướng dẫn hơn
Christian Ransom • Chủ nhật, ngày 26 tháng 7 năm 2015
Trong ví dụ thứ hai trên dòng 7, nó nói
danh sách trả về [0] + tổng [danh sách [1. ]]
có nghĩa là gì" [1. ]" làm gì? Tôi đã xem và không thấy bất cứ điều gì về điều đó ở nơi khác trong hướng dẫn
Frank • Chủ nhật, ngày 26 tháng 7 năm 2015
Xin chào Christian, [1. ] trả về mọi thứ từ ký tự thứ hai
Kết thúc • Thứ Hai, ngày 07 tháng 9 năm 2015
Tôi muốn nói lời cảm ơn vì hướng dẫn tuyệt vời của bạn. cảm ơn. . ]
Frank • Thứ Hai, ngày 07 tháng 9 năm 2015
cảm ơn vây
Fred Pouyet • Thứ 5, ngày 17 tháng 9 năm 2015
Tôi đồng ý với Fin. Cảm ơn rất nhiều vì đã tổng hợp hướng dẫn này, nó rất đơn giản để nắm bắt và không nhàm chán không giống như phần lớn các hướng dẫn