Ai đó có thể giải thích điều này đệ quy cho tôi?

Question

Tôi nhận được mã này từ mã vạch.

class Solution(object): 
    def myPow(self, x, n): 
     if n == 0: 
      return 1 
     if n == -1: 
      return 1/x 
     return self.myPow(x * x, n/2) * ([1, x][n % 2]) 

Mã này được sử dụng để triển khai poe(x, n), có nghĩa là x**n bằng Python.

Tôi muốn biết lý do tại sao có thể triển khai pow(x, n).

Có vẻ không có ý nghĩa ...

Tôi hiểu

if n == 0: 
and 
if n == -1: 

Nhưng mã lõi:

self.myPow(x * x, n/2) * ([1, x][n % 2]) 

thực sự là khó hiểu.

BTW, mã này chỉ hoạt động trên Python 2.7. Nếu bạn muốn thử nghiệm trên Python 3, bạn nên thay đổi

myPow(x*x, n/2) * ([1, x][n % 2]) 

để

myPow(x*x, n // 2) * ([1, x][n % 2]) 

Answer 1

Chức năng đệ quy là để tính toán sức mạnh (có lẽ hầu hết nguyên, không tiêu cực hoặc -1, sức mạnh) của một số, như bạn có thể đã mong đợi (một cái gì đó như x = 2.2 và n = 9).

(Và điều này dường như được viết cho Python 2.x (do kết quả n/2 đã dự kiến ​​của integer thay vì n//2))

Các ban đầu returns rất thẳng thắn toán.

if n == 0: 
    return 1 
if n == -1: 
    return 1/x 

Khi sức mạnh là 0, sau đó bạn quay lại 1 và sau đó sức mạnh là -1, quý khách trở 1/x.

Bây giờ dòng tiếp theo bao gồm hai yếu tố:

self.myPow(x * x, n/2) 
and 
[1, x][n%2] 

Đầu tiên một self.myPow(x * x, n/2) chỉ có nghĩa là bạn muốn chắc suất cao hơn (không 0 hoặc -1) vào một nửa của nó bằng cách bình phương số trợ x

(hầu hết có thể để tăng tốc độ tính toán bằng cách giảm số lượng phép nhân cần thiết - hãy tưởng tượng nếu bạn có trường hợp để tính 2^58. Bằng cách nhân, bạn phải nhân số 58 lần. Nhưng nếu bạn chia nó thành hai lần và giải quyết nó một cách đệ quy, bạn sẽ chỉ có số lượng hoạt động nhỏ hơn).

Ví dụ:

x^8 = (x^2)^4 = y^4 #thus you reduce the number of operation you need to perform 

Ở đây, bạn vượt qua x^2 như là đối số tiếp theo của bạn trong đệ quy (có nghĩa là y) và làm điều đó một cách đệ quy cho đến khi sức mạnh là 0 hoặc -1.

Và điều tiếp theo là bạn nhận được modulo của hai trong số sức mạnh được chia. Điều này là để tạo thành trường hợp cho lẻ trường hợp (nghĩa là, khi điện n là lẻ).

[1,x][n%2] #is 1 when n is even, is x when n is odd 

Nếu n là odd, sau đó bằng cách làm n/2, bạn sẽ mất một x trong quá trình này. Do đó bạn phải bù đắp bằng cách nhân số self.myPow(x * x, n/2) với số x. Nhưng nếu số n của bạn không phải là số lẻ (thậm chí), bạn không bị mất một số x, do đó bạn không cần nhân kết quả theo số x nhưng bằng 1.

minh họa,:

x^9 = (x^2)^4 * x #take a look the x here 

nhưng

x^8 = (x^2)^4 * 1 #take a look the 1 here 

Như vậy, điều này:

[1, x][n % 2] 

là để nhân đệ quy trước bởi một trong hai 1 (cho dù n trường hợp) hoặc x (cho trường hợp lẻ n) d tương đương với biểu thức bậc ba:

1 if n % 2 == 0 else x 

Answer 2

Đây là kỹ thuật phân chia và chinh phục. Việc thực hiện ở trên là một cách nhanh chóng để tính toán lũy thừa. Tại mỗi cuộc gọi, một nửa số phép nhân được loại bỏ.

Giả sử rằng n là chẵn x^n có thể được viết như sau (Nếu n là số lẻ, nó đòi hỏi thêm một nhân)

x^n = (x^2)^(n/2) 
or 
x^n = (x^n/2)^2 

Chức năng hiển thị ở trên thực hiện các phiên bản 1. Thật dễ dàng để triển khai phiên bản thứ hai cũng (tôi đã xóa các trường hợp cơ sở đệ quy bên dưới)

r = self.myPow(x,n/2) 
return r * r * ([1, x][n % 2])