Câu hỏi Đuôi đệ quy là gì?


Trong khi bắt đầu học lisp, tôi đã đi qua thuật ngữ đuôi đệ quy. điều đó có chính xác?


1296
2017-08-31 18:21


gốc


Đối với tò mò: cả trong khi và trong khi đã được trong ngôn ngữ trong một thời gian rất dài. Trong khi đang được sử dụng trong tiếng Anh cổ; trong khi đó là một phát triển tiếng Anh trung lưu trong khi đó. Như liên kết họ có thể hoán đổi cho nhau trong ý nghĩa, nhưng trong khi vẫn chưa sống sót trong tiếng Anh Mỹ chuẩn. - Filip Bartuzi
Có lẽ đã muộn, nhưng đây là một bài viết khá hay về đuôi đệ quy:programmerinterview.com/index.php/recursion/tail-recursion - Sam003
Trước tiên, bạn cần phải hiểu đệ quy. Một bình luận tốt giải thích nó là ở đây: stackoverflow.com/questions/33923/… - joe_young
Một trong những lợi ích to lớn của việc xác định một hàm đệ quy đuôi là nó có thể được chuyển đổi thành một dạng lặp và do đó làm sống lại thuật toán từ phương thức-stack-overhead. Có thể muốn truy cập phản hồi từ @Kyle Cronin và vài người khác bên dưới - KGhatak
@joe_young - Câu chuyện kỳ ​​diệu của đệ quy. Tôi không thể đưa ra bình luận của bạn đủ. Tốt nhất! - RBT


Các câu trả lời:


Hãy xem xét một hàm đơn giản để thêm N số nguyên đầu tiên. (ví dụ. sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Đây là một triển khai JavaScript đơn giản sử dụng đệ quy:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

Nếu bạn gọi recsum(5), đây là những gì trình thông dịch JavaScript sẽ đánh giá:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Lưu ý cách mọi cuộc gọi đệ quy phải hoàn thành trước khi trình thông dịch JavaScript bắt đầu thực sự thực hiện công việc tính tổng.

Đây là phiên bản đệ quy đuôi của cùng một hàm:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Đây là chuỗi các sự kiện sẽ xảy ra nếu bạn gọi tailrecsum(5), (có hiệu quả sẽ là tailrecsum(5, 0), vì đối số thứ hai mặc định).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

Trong trường hợp đệ quy đuôi, với mỗi đánh giá của cuộc gọi đệ quy, running_total đã cập nhật.

Lưu ý: Câu trả lời ban đầu đã sử dụng các ví dụ từ Python. Những thay đổi này đã được thay đổi thành JavaScript, vì hỗ trợ phiên dịch JavaScript hiện đại tối ưu hóa cuộc gọi đuôi nhưng thông dịch viên Python thì không.


1294
2017-08-29 03:57



Python là một lựa chọn kỳ lạ ở đây, vì nó không có loại bỏ đệ quy đuôi AFAIK. - Chris Conway
Chris Conway là chính xác. Các cuộc gọi đuôi không được tối ưu hóa bằng Python, thật không may. Guido tuyên bố có sẵn ngăn xếp để gỡ lỗi tốt hơn TCO. - McPherrinM
Bạn sẽ tìm thấy ý kiến ​​của Guido đây. - new123456
@ Paco, liên kết là gì? Có phải đó là một trò đùa không? Đó là 404, bạn có gương không? :-) - tillda
@tillda: Có một trò đùa. Đây là một tấm gương: cs.cmu.edu/~wklieber/python-tail-recursion.jpg - Paco


Trong sự đệ quy truyền thống, các mô hình điển hình là bạn thực hiện các cuộc gọi đệ quy của bạn đầu tiên, và sau đó bạn lấy giá trị trả về của cuộc gọi đệ quy và tính toán kết quả. Theo cách này, bạn không nhận được kết quả tính toán của mình cho đến khi bạn trở về từ mọi cuộc gọi đệ quy.

Trong đuôi đệ quy, trước tiên bạn thực hiện các phép tính của mình, và sau đó bạn thực hiện cuộc gọi đệ quy, chuyển các kết quả của bước hiện tại của bạn đến bước đệ quy tiếp theo. Điều này dẫn đến tuyên bố cuối cùng ở dạng (return (recursive-function params)). Về cơ bản, giá trị trả về của bất kỳ bước đệ quy nào giống như giá trị trả về của cuộc gọi đệ quy tiếp theo.

Hậu quả của việc này là khi bạn đã sẵn sàng thực hiện bước đệ quy tiếp theo của mình, bạn không cần khung ngăn xếp hiện tại nữa. Điều này cho phép tối ưu hóa một số. Trong thực tế, với trình biên dịch được viết thích hợp, bạn sẽ không bao giờ bị tràn ngăn xếp người cười với một cuộc gọi đệ quy đuôi. Đơn giản chỉ cần tái sử dụng khung stack hiện tại cho bước đệ quy tiếp theo. Tôi khá chắc Lisp làm điều này.


547
2017-08-31 17:29



"Tôi khá chắc chắn Lisp làm điều này" - Đề án nào, nhưng thường Lisp không phải lúc nào. - Aaron
@Daniel "Về cơ bản, giá trị trả về của bất kỳ bước đệ quy nào giống như giá trị trả về của cuộc gọi đệ quy tiếp theo." - Tôi không thấy đối số này giữ đúng cho đoạn mã được đăng bởi Lorin Hochstein. Bạn có thể vui lòng xây dựng? - Geek
@ Geek Đây là một phản ứng thực sự muộn, nhưng điều đó thực sự đúng trong ví dụ của Lorin Hochstein. Việc tính toán cho mỗi bước được thực hiện trước cuộc gọi đệ quy, thay vì sau đó. Kết quả là, mỗi điểm dừng chỉ trả về giá trị trực tiếp từ bước trước đó. Cuộc gọi đệ quy cuối cùng kết thúc tính toán và sau đó trả về kết quả cuối cùng chưa được sửa đổi tất cả các cách quay trở lại ngăn xếp cuộc gọi. - reirab
Scala có nhưng bạn cần @tailrec được chỉ định để thực thi nó. - SilentDirge
"Theo cách này, bạn không nhận được kết quả tính toán của bạn cho đến khi bạn đã trở về từ mọi cuộc gọi đệ quy." - có lẽ tôi đã hiểu nhầm điều này, nhưng điều này không thực sự đúng với các ngôn ngữ lười biếng sự đệ quy truyền thống là cách duy nhất để thực sự nhận được kết quả mà không cần gọi tất cả các lần thu thập lại (ví dụ: gấp trên danh sách vô hạn các Bools với &&). - hasufell


Một điểm quan trọng là đệ quy đuôi về cơ bản là tương đương với vòng lặp. Nó không chỉ là vấn đề tối ưu hóa trình biên dịch, mà là một thực tế cơ bản về tính biểu cảm. Điều này đi theo cả hai cách: bạn có thể lấy bất kỳ vòng lặp nào của biểu mẫu

while(E) { S }; return Q

Ở đâu E và Q là biểu thức và S là một chuỗi các câu lệnh và biến nó thành một hàm đệ quy đuôi

f() = if E then { S; return f() } else { return Q }

Tất nhiên, E, SQ phải được xác định để tính toán một số giá trị thú vị trên một số biến. Ví dụ, hàm lặp

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

tương đương với các hàm đệ quy đuôi (s)

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Điều này "gói" của hàm đệ quy đuôi với hàm có ít thông số hơn là một thành ngữ chức năng phổ biến.)


165
2017-08-29 16:03



Lời giải thích tuyệt vời, nhưng tại sao chức năng của bạn được gọi là fibo? Đó không phải là Fibonacci; nó là f (n) = nhị thức (n + 1,2) - RexE
@ RexE Tổng fart não. Tôi đã upvoted 20 lần và không ai chỉ ra rằng! - Chris Conway
:) cũng đảm bảo đổi tên các cuộc gọi đệ quy. - RexE
Trong câu trả lời của @LorinHochstein, tôi hiểu, dựa trên lời giải thích của anh ta, cái đuôi đệ quy đó là khi phần đệ quy theo "Return", tuy nhiên trong phần của bạn, đệ quy đuôi thì không. Bạn có chắc chắn ví dụ của bạn được xem xét đúng là đệ quy đuôi không? - CodyBugstein
@Imray Phần đệ quy đuôi là câu lệnh "return sum_aux" bên trong sum_aux. - Chris Conway


Trích đoạn này từ sách Lập trình ở Lua trình diễn làm thế nào để thực hiện một đệ quy đuôi thích hợp (trong Lua, nhưng nên áp dụng cho Lisp quá) và tại sao nó tốt hơn.

A cuộc gọi đuôi [đuôi đệ quy] là một loại goto mặc quần áo   như một cuộc gọi. Một cuộc gọi đuôi sẽ xảy ra khi   chức năng gọi khác là lần cuối   hành động, vì vậy nó không có gì khác để làm.   Ví dụ, trong đoạn mã sau,   cuộc gọi đến g là một cuộc gọi đuôi:

function f (x)
  return g(x)
end

Sau f cuộc gọi g, nó không có gì khác   làm. Trong những tình huống như vậy, chương trình   không cần phải quay lại cuộc gọi   hàm khi hàm được gọi   kết thúc. Do đó, sau cuộc gọi đuôi,   chương trình không cần giữ bất kỳ   thông tin về chức năng gọi   trong ngăn xếp. ...

Bởi vì một cuộc gọi đuôi thích hợp không sử dụng   ngăn xếp không gian, không có giới hạn về   số đuôi "lồng nhau" gọi là   chương trình có thể thực hiện. Ví dụ, chúng ta có thể   gọi hàm sau với bất kỳ   số làm đối số; nó sẽ không bao giờ   tràn ngăn xếp:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... Như tôi đã nói trước đó, một cuộc gọi đuôi là một   loại goto. Như vậy, khá hữu ích   ứng dụng các cuộc gọi đuôi thích hợp trong   Lua là dành cho các máy trạng thái lập trình.   Các ứng dụng này có thể đại diện cho từng ứng dụng   nhà nước bởi một chức năng; thay đổi trạng thái   là để đi đến (hoặc gọi) một   chức năng. Ví dụ, hãy cho chúng tôi   xem xét một trò chơi mê cung đơn giản. Mê cung   có một số phòng, mỗi phòng có tối đa   bốn cửa: bắc, nam, đông, và   hướng Tây. Tại mỗi bước, người dùng nhập   hướng di chuyển. Nếu có cửa   theo hướng đó, người dùng truy cập   phòng tương ứng; nếu không   chương trình in một cảnh báo. Mục đích là   đi từ phòng ban đầu đến chung kết   phòng.

Trò chơi này là một máy trạng thái điển hình,   nơi phòng hiện tại là tiểu bang.   Chúng ta có thể thực hiện mê cung như vậy với một   chức năng cho mỗi phòng. Chúng tôi sử dụng đuôi   cuộc gọi di chuyển từ một phòng đến   khác. Một mê cung nhỏ với bốn phòng   có thể trông như thế này:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Vì vậy, bạn thấy, khi bạn thực hiện một cuộc gọi đệ quy như:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Đây không phải là đệ quy đuôi vì bạn vẫn có những việc cần làm (thêm 1) trong hàm đó sau khi thực hiện cuộc gọi đệ quy. Nếu bạn nhập một số rất cao nó có thể sẽ gây ra một tràn ngăn xếp.


110
2017-08-29 03:55



Đây là một câu trả lời tuyệt vời vì nó giải thích các tác động của các cuộc gọi đuôi khi kích thước ngăn xếp. - Andrew Swan
@AndrewSwan Thật vậy, mặc dù tôi tin rằng người hỏi ban đầu và người đọc thỉnh thoảng có thể vấp ngã vào câu hỏi này có thể được phục vụ tốt hơn với câu trả lời được chấp nhận (vì anh ta có thể không biết chồng thực sự là gì.) Bằng cách tôi sử dụng Jira, lớn quạt. - Hoffmann
Câu trả lời yêu thích của tôi cũng là do bao hàm ý nghĩa cho kích thước ngăn xếp. - njk2015


Sử dụng đệ quy thông thường, mỗi cuộc gọi đệ quy đẩy một mục khác vào ngăn xếp cuộc gọi. Khi đệ quy được hoàn thành, ứng dụng sau đó phải bật mỗi mục nhập tắt tất cả các cách quay trở lại.

Với đệ quy đuôi, trình biên dịch có thể thu gọn ngăn xếp xuống một mục, vì vậy bạn tiết kiệm không gian ngăn xếp ... Một truy vấn đệ quy lớn thực sự có thể gây ra tràn ngăn xếp.

Về cơ bản Tail recursions có thể được tối ưu hóa vào iteration.


57
2017-08-29 03:57





Thay vì giải thích nó bằng lời nói, đây là một ví dụ. Đây là một phiên bản Đề án của hàm giai thừa:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Đây là một phiên bản giai thừa có tính đệ quy đuôi:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Bạn sẽ nhận thấy trong phiên bản đầu tiên mà các đệ quy gọi đến thực tế được đưa vào biểu thức phép nhân, và do đó nhà nước phải được lưu trên ngăn xếp khi thực hiện cuộc gọi đệ quy. Trong phiên bản đệ quy đuôi không có biểu thức S khác đang đợi giá trị của cuộc gọi đệ quy, và vì không còn việc gì để làm, trạng thái không phải được lưu trên ngăn xếp. Như một quy luật, các hàm đệ quy đệ quy sử dụng không gian ngăn xếp không đổi.


56
2017-08-29 07:21



1 để đề cập đến khía cạnh quan trọng nhất của việc thu thập đuôi mà chúng có thể được chuyển đổi thành dạng lặp lại và do đó biến nó thành dạng phức tạp bộ nhớ O (1). - KGhatak
@KGhatak không chính xác; câu trả lời chính xác nói về "không gian ngăn xếp liên tục", không phải bộ nhớ nói chung. không được nitpicking, chỉ để đảm bảo không có sự hiểu lầm. ví dụ. -sự biến đổi đuôi danh sách đuôi list-reverse thủ tục sẽ chạy trong không gian ngăn xếp liên tục nhưng sẽ tạo và phát triển một cấu trúc dữ liệu trên heap. Việc di chuyển cây có thể sử dụng chồng được mô phỏng, trong một đối số bổ sung. v.v. - Will Ness


Các tập tin biệt ngữ có điều này để nói về định nghĩa của đệ quy đuôi:

đuôi đệ quy /n./

Nếu bạn không bị bệnh của nó, xem đuôi đệ quy.


52
2017-08-29 03:57



Tôi thấy những gì bạn đã làm ở đó. Ví dụ táo bạo ở đó. : D - Sajib Acharya
Giá trị hài lòng thêm và upvotes trên bài này bù đắp cho thực tế rằng đây không phải là một câu trả lời. - Eric Leschinski
Tôi nghiêm túc, không thấy cái này đến. - Mehraj Malik


Đuôi đệ quy đề cập đến các cuộc gọi đệ quy được cuối cùng trong hướng dẫn logic cuối cùng trong thuật toán đệ quy.

Thông thường trong đệ quy bạn có một trường hợp cơ bản đó là những gì dừng các cuộc gọi đệ quy và bắt đầu popping stack cuộc gọi. Để sử dụng một ví dụ cổ điển, mặc dù C-ish nhiều hơn Lisp, hàm giai thừa minh họa cho đệ quy đuôi. Cuộc gọi đệ quy xảy ra sau kiểm tra tình trạng cơ sở.

factorial(x, fac) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Lưu ý, cuộc gọi đầu tiên đến giai thừa phải là giai thừa (n, 1) trong đó n là số mà giai thừa được tính toán.


23
2017-08-31 23:52