Làm thế nào để nhận ra cái gì là gì, và cái gì không phải là đệ quy đuôi?

Question

Đôi khi nó đủ đơn giản (nếu cuộc gọi tự là tuyên bố cuối cùng, đó là đệ quy đuôi), nhưng vẫn có những trường hợp làm tôi bối rối. Một giáo sư nói với tôi rằng "nếu không có hướng dẫn để thực hiện sau khi tự gọi, đó là đệ quy đuôi". Làm thế nào về những ví dụ này (bỏ qua thực tế là chúng không có ý nghĩa nhiều):

a) Điều này nên được đệ quy đuôi, xem cách tự gọi là tuyên bố cuối cùng và không có gì để thực hiện sau nó .

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else 
     return foo(n-2); 
} 

b) Nhưng còn cái này thì sao? Nó sẽ là một cuộc gọi đuôi, bởi vì nếu điều kiện là đúng, không có gì ngoại trừ nó sẽ được thực hiện, nhưng nó không phải là tuyên bố cuối cùng?

function foo(n) 
{ 
    if(n != 0) 
     return foo(n-2); 
    else 
     return 0; 
} 

c) Cái này thì sao? Trong cả hai trường hợp, cuộc gọi tự thực hiện sẽ là điều cuối cùng được thực thi:

function foo(n) 
{ 
    if(n == 0) 
     return 0; 
    else  
    { 
     if(n > 100) 
      return foo(n - 2); 
     else 
      return foo(n - 1); 
    } 
} 

Answer 1

Nó có thể giúp bạn suy nghĩ về điều này về cách tối ưu hóa cuộc gọi đuôi thực sự được triển khai. Đó không phải là một phần của định nghĩa, tất nhiên, nhưng nó thúc đẩy định nghĩa.

Thông thường khi một hàm được gọi, mã gọi sẽ lưu trữ bất kỳ giá trị đăng ký nào mà nó sẽ cần sau này, trên ngăn xếp. Nó cũng sẽ lưu một địa chỉ trả về, cho biết lệnh tiếp theo sau cuộc gọi. Nó sẽ làm bất cứ điều gì nó cần làm để đảm bảo rằng con trỏ ngăn xếp được thiết lập chính xác cho các callee. Sau đó, nó sẽ nhảy đến địa chỉ đích [*] (trong trường hợp này, cùng chức năng). Ngày trở lại, nó biết giá trị trả về là ở nơi được quy định bởi quy ước gọi (đăng ký hoặc ngăn xếp ngăn xếp).

Để biết cuộc gọi đuôi, người gọi không thực hiện việc này. Nó bỏ qua bất kỳ giá trị đăng ký nào, bởi vì nó biết nó sẽ không cần chúng sau này. Nó thiết lập con trỏ ngăn xếp để các callee sẽ sử dụng cùng một ngăn xếp người gọi đã làm, và nó không thiết lập chính nó như là địa chỉ trả về, nó chỉ nhảy đến địa chỉ đích.Do đó, callee sẽ ghi đè lên cùng một vùng stack, nó sẽ đặt giá trị trả về của nó trong cùng một vị trí mà người gọi sẽ đặt giá trị trả về của nó, và khi nó trả về, nó sẽ không trả về người gọi, nhưng sẽ quay lại người gọi người gọi.

Do đó, không chính thức, hàm sẽ đệ quy đuôi khi có thể tối ưu hóa cuộc gọi đuôi và khi đích của cuộc gọi đuôi là chính hàm đó. Hiệu ứng nhiều hơn hoặc ít hơn giống như chức năng chứa một vòng lặp, và thay vì gọi chính nó, cuộc gọi đuôi nhảy đến đầu vòng lặp. Điều này có nghĩa là không có biến cần thiết sau khi cuộc gọi (và thực sự không "làm việc", mà trong một ngôn ngữ như C++ có nghĩa là không có gì bị hủy), và giá trị trả về của cuộc gọi đuôi phải được trả về bởi người gọi.

Đây là tất cả để đệ quy đuôi đơn giản/tầm thường. Có các phép biến đổi có thể được sử dụng để tạo ra một cái gì đó có tính đệ quy không được, ví dụ giới thiệu các tham số phụ, lưu trữ một số thông tin được sử dụng bởi mức đệ quy "dưới cùng", để thực hiện công việc mà nếu không sẽ được thực hiện "lối thoát". Vì vậy, ví dụ:

int triangle(int n) { 
    if (n == 0) return 0; 
    return n + triangle(n-1); 
} 

thể được thực hiện đuôi-đệ quy, hoặc bằng cách lập trình viên hoặc tự động bởi một trình biên dịch đủ thông minh, như thế này:

int triangle(int n, int accumulator = 0) { 
    if (n == 0) return accumulator; 
    return triangle(n-1, accumulator + n); 
} 

Do đó, chức năng cũ có thể được mô tả như " đuôi đệ quy "bởi một người nói về một ngôn ngữ đủ thông minh/trình biên dịch. Hãy chuẩn bị cho việc sử dụng biến thể đó.

[*] Lưu trữ địa chỉ trả lại, di chuyển con trỏ ngăn xếp và nhảy, có thể hoặc không được gói trong một mã vạch duy nhất bởi kiến ​​trúc, nhưng ngay cả khi đó không phải là điều thường xảy ra.

Answer 2

Yep; Tôi nghĩ rằng giáo sư của bạn có nghĩa rằng trong bất kỳ con đường nào, nếu lệnh cuối cùng là đệ quy, thì đó là đệ quy đuôi.

Vì vậy, cả ba ví dụ đều có tính đệ quy đuôi.

Answer 3

Tất cả các chức năng của bạn đều có đuôi đệ quy.

không hướng dẫn còn lại sau khi tự gọi

có nghĩa là: Sau khi tự gọi, bạn trở về từ chức năng, tức là mã không có được thực thi, và không phải là có không còn dòng mã nào trong hàm.

Answer 4

Cả ba ví dụ đều có đuôi đệ quy. Nói chung, nó là đệ quy đuôi, nếu kết quả của hàm (biểu thức sau từ khóa "return") là một cuộc gọi đơn lẻ đến chính hàm đó. Không có nhà điều hành nào khác phải tham gia ở cấp ngoài cùng của biểu thức. Nếu cuộc gọi đến chính nó chỉ là một phần của một biểu thức thì máy phải thực hiện cuộc gọi nhưng sau đó phải quay trở lại vào việc đánh giá biểu thức đã nói, nghĩa là, nó không ở đuôi của việc thực hiện hàm nhưng ở giữa một biểu thức. Tuy nhiên, điều này không áp dụng cho bất kỳ thông số nào mà cuộc gọi đệ quy có thể thực hiện: bất kỳ điều gì được cho phép ở đó, bao gồm cả các cuộc gọi đệ quy cho chính nó (ví dụ: "return foo (foo (0));"). Việc tối ưu hóa các cuộc gọi để nhảy chỉ có thể thực hiện cho cuộc gọi bên ngoài, tất nhiên.