làm thế nào để xác định đầu ra của hàm đệ quy phức tạp bằng tay

Question

Dưới đây là đoạn code đệ quy trong câu hỏi:

def trace(a, b): 
    if (a > b): 
     return -1 
    elif (a == b): 
     print (a * a) 
     return a * a 
    else: 
     m = (a + b)/2 
     return trace (a, m) + trace (m + 1, b) 

x=trace(1,4) 

trong khi tôi không chắc chắn những gì chức năng này là nghĩa vụ phải làm, chúng ta có nghĩa vụ phải tìm đầu ra của x=trace(1,4) cùng với giá trị của x, bằng tay (nghĩa là chúng ta không thể sử dụng nhàn rỗi để giúp chúng ta).

Sau một thời gian, tôi xác định rằng hàm sẽ in 1 và 12.25, sẽ là đầu ra khi gán x thành trace(1,4).

Tuy nhiên, tôi không biết cách xác định giá trị của X sẽ là bao nhiêu. Mặc dù câu trả lời là -91,75, tôi không có manh mối nhỏ như thế nào nó có nguồn gốc (mặc dù tôi biết làm thế nào, nó sẽ mất lứa tuổi để đến với câu trả lời này, và tôi không chắc chắn làm thế nào chúng ta có thể nhanh chóng đến với giải pháp trong một khoảng thời gian ngắn như khi viết bài kiểm tra).

Cảm ơn trước sự giúp đỡ của bạn!

Answer 1

có một cái nhìn tại những dòng này:

m = (a + b)/2 
return trace(a, m) + ... 

những dòng này chỉ được thực hiện nếu b lớn hơn a. Điều đó có nghĩa là m sẽ luôn lớn hơn a và cuộc gọi hàm đệ quy đầu tiên có cùng một vấn đề. Với các giá trị a = 1 và b > a, m hội tụ thành 1. Về lý thuyết, đệ quy không bao giờ kết thúc kể từ m sẽ không bao giờ là 1.0 trở xuống. Tuy nhiên, độ chính xác phao bị hạn chế do đó có một điểm (sau nhiều lần gọi đệ quy), nơi bộ xử lý không thể khác nhau m từ 1.0. Tại thời điểm này, elif (a == b): trở thành sự thật và dừng đệ quy. Điều đó không giải thích tại sao kết quả là -91.75, nhưng nó cho thấy lý do tại sao nó gần như không thể hiển thị tất cả các cuộc gọi đệ quy trong một sơ đồ hoặc cây hoặc sth. Tôi hy vọng nó sẽ giúp.

Answer 2

Trước hết, tôi đã lừa. Với bộ ngực của tôi ở đây là một số gợi ý: Chức năng này chắc chắn không dành cho Python 3! Lý do là toán tử /. Trong Python 2 nó dẫn đến số nguyên trong Python3 nó kết quả nổi. Vì vậy, lưu ý điều kiện tiên quyết này ở đây là giải pháp của tôi:

Chức năng này không phức tạp. Kiểu dữ liệu của mỗi biến và tất cả các biến của bạn là số nguyên! m sẽ luôn là một số nguyên. x là 30. Mức đệ quy là ba, bằng bảy cuộc gọi đến hàm của bạn (bao gồm cả hàm đầu tiên). Và đây là cách bạn đi về những thứ như thế này: Lấy một số giấy và một cây bút và chỉ viết xuống từng bước.

1. Đầu vào là: a = 1 và b = 4 dẫn đến phần khác trong chức năng của bạn ... không có đầu ra cho đến thời điểm này. Có m được tính là (1 + 4)/2. Trong cuốn sách của tôi là 2,5. Nhưng điều này được làm tròn thành 2, bởi vì chúng ta có số nguyên. Sau đó, đệ quy bắt đầu bằng hai cuộc gọi (1,2) và (3,4)
2. Hãy xem (1,2): a = 1 và b = 2. Một lần nữa, không có đầu ra và chúng ta đi đến phần khác: m được tính là 3/2, là 1,5 được làm tròn thành 1. Một lần nữa hai hàm của hàm có tham số mới (1,1) và (2, 2). Lưu ý rằng cả hai cuộc gọi bây giờ sẽ nhập phần elif của hàm và mỗi cuộc gọi sẽ tạo ra một đầu ra và một giá trị trả lại. Bạn có thể thay thế (1,1) bằng 1 và (2,2) với 4. Phép đệ quy được thực hiện ở đây, và kết quả của dấu vết (1,2) trong 5. Hãy nhìn vào nhánh khác của đệ quy.
3. Đầu vào là = 3 và b = 4 dẫn đến một cặp cuộc gọi khác với các thông số sau: (3,3) và (4,4). Tôi nghĩ rằng bây giờ bạn sẽ nhận được hang của nó. Phần thú vị là cộng tất cả các giá trị trả lại theo cách chúng được cung cấp.

Làm như thế nào: Nó tổng hợp tất cả các ô của tất cả các số nguyên giữa a và b.