Tôi có một hàm đệ quy cố gắng tạo thành một khoản tiền nhất định được đưa ra một danh sách các số nguyên. Các chức năng hoạt động nhưng nó cung cấp cho tôi tất cả các giải pháp có thể. Tôi muốn thoát ra khỏi chức năng đệ quy sau khi tìm thấy một giải pháp. Làm thế nào tôi có thể làm điều đó? Dưới đây là mã [giả-] cho hàm:
function find_sum[list_of_integers, target_sum, partial_solution]:
if partial_solutions == target_sum:
return True
if partial_solution > target_sum:
return
for i in range[len[list_of_integers]]:
n = list_of_integers[i]
remaining = list_of_integers[i+1:]
find_sum[remaining, target_sum, partial_solution + n]
Vì vậy, tôi chỉ muốn biết liệu Target_Sum có thể được hình thành bởi danh sách các số nguyên hay không, tôi không cần tất cả các giải pháp.
Hỏi ngày 25 tháng 4 năm 2015 lúc 10:12Apr 25, 2015 at 10:12
Bạn cần kiểm tra giá trị trả về của cuộc gọi đệ quy; Nếu True được trả lại, tuyên truyền đó ngay lập tức thay vì tiếp tục lặp lại:
for i in range[len[list_of_integers]]:
n = list_of_integers[i]
remaining = list_of_integers[i+1:]
found = find_sum[remaining, target_sum, partial_solution + n]
if found:
return True
Đã trả lời ngày 25 tháng 4 năm 2015 lúc 10:14Apr 25, 2015 at 10:14
Martijn Pieters ♦ Martijn Pieters♦Martijn Pieters
995K277 Huy hiệu vàng3920 Huy hiệu bạc3261 Huy hiệu Đồng277 gold badges3920 silver badges3261 bronze badges
0
Bạn có thể sử dụng lớp học. Khởi tạo một biến self.flag = false trong phương thức init, khi bạn tìm thấy giải pháp thay đổi self.flag = true và không trả về khi self.flag là đúng.init method, when you find the solution change self.flag = True and return None when self.flag is True.
class Solution:
def __init__[self]:
self.flag = False
def find_sum[....]:
for i in range[len[list_of_integers]]:
if self.flag: return True
n = list_of_integers[i]
remaining = list_of_integers[i+1:]
self.flag = find_sum[remaining, target_sum, partial_solution + n]
Đã trả lời ngày 23 tháng 9 năm 2020 lúc 4:50Sep 23, 2020 at 4:50
Theja mtheja mTheja M
Huy hiệu 641 Bạc1 Huy hiệu Đồng1 silver badge1 bronze badge
Khi bạn tìm thấy giải pháp chỉ cần trả lại và sử dụng sys.exit [0] ngay trong dòng tiếp theo, nó sẽ dừng các cuộc gọi đệ quy thêm và đưa bạn ra ngay lập tức.
Đã trả lời ngày 9 tháng 10 năm 2019 lúc 12:42Oct 9, 2019 at 12:42
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].
Đệ 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 Python
Trong 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à recurse.
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
def factorial[x]:
"""This is a recursive function
to find the factorial of an integer"""
if x == 1:
return 1
else:
return [x * factorial[x-1]]
num = 3
print["The factorial of", num, "is", factorial[num]]Đầu ra
The factorial of 3 is 6
Trong ví dụ trên,
for i in range[len[list_of_integers]]:
n = list_of_integers[i]
remaining = list_of_integers[i+1:]
found = find_sum[remaining, target_sum, partial_solution + n]
if found:
return True
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
for i in range[len[list_of_integers]]:
n = list_of_integers[i]
remaining = list_of_integers[i+1:]
found = find_sum[remaining, target_sum, partial_solution + n]
if found:
return True
def recursor[]:
recursor[]
recursor[]Đầu ra
Traceback [most recent call last]: File "", line 3, in File "", line 2, in a File "", line 2, in a File "", line 2, in a [Previous line repeated 996 more times] RecursionError: maximum recursion depth exceeded
Ưu điểm của đệ quy
- Các chức năng đệ quy làm cho mã trông sạch sẽ và thanh lịch.
- Một nhiệm vụ phức tạp có thể được chia thành các vấn đề phụ đơn giản hơn bằng cách sử dụng đệ quy.
- Tạo trình tự dễ dàng hơn với đệ quy hơn là sử dụng một số lần lặp lồng nhau.
Nhược điểm của đệ quy
- Đôi khi logic đằng sau đệ quy là khó theo dõi.
- Các cuộc gọi đệ quy là tốn kém [không hiệu quả] vì chúng chiếm rất nhiều bộ nhớ và thời gian.
- Các chức năng đệ quy rất khó để gỡ lỗi.