Hiểu cách các hàm đệ quy hoạt động?

1. Hàm được gọi đệ quy cho đến khi một điều kiện được đáp ứng. Điều kiện đó là a > b. Khi điều kiện này được đáp ứng, trả về 0. Thoạt nhìn, tôi sẽ mong giá trị trả về là 0 rõ ràng là không chính xác.

Đây là những gì máy tính sumInts(2,5)sẽ nghĩ nếu nó có thể:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

Như bạn thấy, một số lệnh gọi hàm sumIntsthực sự trả về 0 tuy nhiên đây không phải là giá trị cuối cùng vì máy tính vẫn phải thêm 5 vào 0 đó, sau đó 4 vào kết quả, sau đó 3, rồi 2, như được mô tả bởi bốn câu cuối cùng của những suy nghĩ của máy tính của chúng tôi. Lưu ý rằng trong đệ quy, máy tính không chỉ phải tính toán cuộc gọi đệ quy mà còn phải nhớ phải làm gì với giá trị được trả về bởi cuộc gọi đệ quy. Có một vùng đặc biệt của bộ nhớ máy tính được gọi là ngăn xếp nơi loại thông tin này được lưu, không gian này bị giới hạn và các chức năng quá đệ quy có thể làm cạn kiệt ngăn xếp: đây là ngăn xếp tràn đặt tên cho trang web yêu thích nhất của chúng tôi.

Tuyên bố của bạn dường như đưa ra giả định ngầm định rằng máy tính quên mất những gì đã xảy ra khi thực hiện cuộc gọi đệ quy, nhưng không, đây là lý do tại sao kết luận của bạn không phù hợp với quan sát của bạn.

2. In ra giá trị 'a' trên mỗi lần lặp mang lại giá trị mà tôi mong đợi: 2, 3, 4, 5 (tại điểm 5 + 1> b đáp ứng điều kiện đầu tiên: a> b) nhưng tôi vẫn không thấy giá trị của 14 đạt được.

Điều này là do giá trị trả về không phải là achính nó mà là tổng giá trị avà giá trị được trả về bởi lệnh gọi đệ quy.

Để hiểu đệ quy bạn phải nghĩ vấn đề theo một cách khác. Thay vì một chuỗi các bước logic hợp lý có ý nghĩa như toàn bộ bạn thay vào đó là một vấn đề lớn và chia thành các vấn đề nhỏ hơn và giải quyết chúng, khi bạn có câu trả lời cho các vấn đề phụ, bạn kết hợp các kết quả của các vấn đề phụ để thực hiện giải pháp cho vấn đề lớn hơn. Hãy nghĩ về bạn và bạn bè của bạn cần đếm số viên bi trong một cái xô lớn. Bạn thực hiện mỗi lần lấy một thùng nhỏ hơn và đếm từng cái một và khi bạn hoàn thành, bạn cộng các tổng lại với nhau .. Bây giờ nếu mỗi bạn tìm thấy một số người bạn và chia các thùng hơn nữa, thì bạn chỉ cần đợi những người bạn khác này Tìm ra tổng số của họ, mang nó trở lại cho mỗi bạn, bạn thêm nó lên. Và như vậy.

Bạn phải nhớ mỗi khi hàm gọi chính nó một cách đệ quy, nó tạo ra một bối cảnh mới với một tập hợp con của vấn đề, một khi phần đó được giải quyết, nó sẽ được trả về để lần lặp trước có thể hoàn thành.

Hãy để tôi chỉ cho bạn các bước:

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

khi sumInts (a: 6, b: 5) đã được thực thi, kết quả có thể được tính toán để quay lại chuỗi với kết quả bạn nhận được:

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

Một cách khác để biểu diễn cấu trúc của đệ quy:

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

Đệ quy là một chủ đề khó hiểu và tôi không nghĩ rằng tôi hoàn toàn có thể thực hiện công lý ở đây. Thay vào đó, tôi sẽ cố gắng tập trung vào đoạn mã cụ thể mà bạn có ở đây và cố gắng mô tả cả trực giác về lý do giải pháp hoạt động và cơ chế về cách mã tính toán kết quả của nó.

Mã bạn đã đưa ra ở đây giải quyết vấn đề sau: bạn muốn biết tổng của tất cả các số nguyên từ a đến b, bao gồm. Ví dụ của bạn, bạn muốn tổng các số từ 2 đến 5, bao gồm, đó là

2 + 3 + 4 + 5

Khi cố gắng giải quyết vấn đề một cách đệ quy, một trong những bước đầu tiên là tìm ra cách chia nhỏ vấn đề thành một vấn đề nhỏ hơn với cùng cấu trúc. Vì vậy, giả sử rằng bạn muốn tổng hợp các số từ 2 đến 5, bao gồm. Một cách để đơn giản hóa điều này là lưu ý rằng tổng trên có thể được viết lại thành

2 + (3 + 4 + 5)

Ở đây, (3 + 4 + 5) là tổng của tất cả các số nguyên nằm trong khoảng từ 3 đến 5. Nói cách khác, nếu bạn muốn biết tổng của tất cả các số nguyên từ 2 đến 5, hãy bắt đầu bằng cách tính tổng của tất cả các số nguyên trong khoảng từ 3 đến 5, sau đó thêm 2.

Vậy làm thế nào để bạn tính tổng của tất cả các số nguyên từ 3 đến 5, bao gồm? Chà, tổng đó là

3 + 4 + 5

thay vào đó có thể được coi là

3 + (4 + 5)

Ở đây, (4 + 5) là tổng của tất cả các số nguyên từ 4 đến 5, bao gồm. Vì vậy, nếu bạn muốn tính tổng của tất cả các số từ 3 đến 5, bao gồm, bạn sẽ tính tổng của tất cả các số nguyên từ 4 đến 5, sau đó thêm 3.

Có một mô hình ở đây! Nếu bạn muốn tính tổng các số nguyên giữa a và b, đã bao gồm, bạn có thể làm như sau. Đầu tiên, tính tổng các số nguyên giữa a + 1 và b, đã bao gồm. Tiếp theo, thêm một vào tổng số đó. Bạn sẽ nhận thấy rằng "tính tổng các số nguyên giữa a + 1 và b, bao gồm" xảy ra khá giống với loại vấn đề chúng tôi đã cố gắng giải quyết, nhưng với các tham số hơi khác nhau. Thay vì tính toán từ a đến b, bao gồm, chúng tôi tính toán từ +1 đến b, bao gồm. Đó là bước đệ quy - để giải quyết vấn đề lớn hơn ("tổng từ a đến b, bao gồm"), chúng tôi giảm vấn đề thành phiên bản nhỏ hơn của chính nó ("tổng từ 1 đến 1, bao gồm.").

Nếu bạn xem mã bạn có ở trên, bạn sẽ nhận thấy rằng có bước này trong đó:

return a + sumInts(a + 1, b: b)

Mã này chỉ đơn giản là một bản dịch của logic trên - nếu bạn muốn tính tổng từ a đến b, bao gồm, hãy bắt đầu bằng cách tính tổng + 1 đến b, bao gồm (đó là cuộc gọi đệ quy đến sumInts), sau đó thêm a.

Tất nhiên, tự nó phương pháp này sẽ không thực sự hiệu quả. Ví dụ, làm thế nào bạn sẽ tính tổng của tất cả các số nguyên từ 5 đến 5 bao gồm? Vâng, bằng cách sử dụng logic hiện tại của chúng tôi, bạn sẽ tính tổng của tất cả các số nguyên từ 6 đến 5, sau đó thêm 5. Vậy làm thế nào để bạn tính tổng của tất cả các số nguyên từ 6 đến 5, bao gồm? Chà, sử dụng logic hiện tại của chúng tôi, bạn sẽ tính tổng của tất cả các số nguyên từ 7 đến 5, bao gồm, sau đó thêm 6. Bạn sẽ nhận thấy một vấn đề ở đây - điều này cứ tiếp tục và tiếp tục!

Trong giải quyết vấn đề đệ quy, cần có một số cách để ngừng đơn giản hóa vấn đề và thay vào đó chỉ cần giải quyết trực tiếp. Thông thường, bạn sẽ tìm thấy một trường hợp đơn giản trong đó câu trả lời có thể được xác định ngay lập tức, sau đó cấu trúc giải pháp của bạn để giải quyết trực tiếp các trường hợp đơn giản khi chúng phát sinh. Điều này thường được gọi là trường hợp cơ sở hoặc cơ sở đệ quy .

Vì vậy, trường hợp cơ bản trong vấn đề cụ thể này là gì? Khi bạn tính tổng các số nguyên từ a đến b, bao gồm, nếu a xảy ra lớn hơn b, thì câu trả lời là 0 - không có bất kỳ số nào trong phạm vi! Do đó, chúng tôi sẽ cấu trúc giải pháp của chúng tôi như sau:

1. Nếu a> b, thì câu trả lời là 0.
2. Mặt khác (a ≤ b), nhận câu trả lời như sau:
   1. Tính tổng các số nguyên giữa a + 1 và b.
   2. Thêm một để có được câu trả lời.

Bây giờ, so sánh mã giả này với mã thực tế của bạn:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

Lưu ý rằng gần như chính xác một bản đồ một-một giữa giải pháp được nêu trong mã giả và mã thực tế này. Bước đầu tiên là trường hợp cơ sở - trong trường hợp bạn yêu cầu tổng một dãy số trống, bạn nhận được 0. Nếu không, hãy tính tổng giữa a + 1 và b, sau đó đi thêm a.

Cho đến nay, tôi chỉ đưa ra một ý tưởng cấp cao đằng sau mã. Nhưng bạn đã có hai câu hỏi khác, rất tốt. Đầu tiên, tại sao điều này không luôn luôn trả về 0, với điều kiện là hàm trả về 0 nếu a> b? Thứ hai, 14 thực sự đến từ đâu? Chúng ta hãy lần lượt xem xét những thứ này.

Hãy thử một trường hợp rất, rất đơn giản. Điều gì xảy ra nếu bạn gọi sumInts(6, 5)? Trong trường hợp này, theo dõi mã, bạn thấy rằng hàm chỉ trả về 0. Đó là điều đúng đắn để làm - không có bất kỳ số nào trong phạm vi. Bây giờ, hãy thử một cái gì đó khó hơn. Điều gì xảy ra khi bạn gọi sumInts(5, 5)? Vâng, đây là những gì xảy ra:

1. Bạn gọi sumInts(5, 5). Chúng ta rơi vào elsenhánh, trả về giá trị của `a + sumInts (6, 5).
2. Để sumInts(5, 5)xác định xem đó sumInts(6, 5)là gì , chúng tôi cần tạm dừng những gì chúng tôi đang làm và thực hiện cuộc gọi đến sumInts(6, 5).
3. sumInts(6, 5)được gọi. Nó vào ifchi nhánh và trở về 0. Tuy nhiên, trường hợp này sumIntsđược gọi bởi sumInts(5, 5), vì vậy giá trị trả về được truyền lại sumInts(5, 5), chứ không phải cho người gọi cấp cao nhất.
4. sumInts(5, 5)Bây giờ có thể tính toán 5 + sumInts(6, 5)để lấy lại 5. Sau đó, nó trả lại cho người gọi cấp cao nhất.

Lưu ý cách giá trị 5 được hình thành ở đây. Chúng tôi bắt đầu với một cuộc gọi hoạt động đến sumInts. Điều đó đã loại bỏ một cuộc gọi đệ quy khác và giá trị được trả về bởi cuộc gọi đó đã truyền đạt thông tin trở lại sumInts(5, 5). Cuộc gọi đến sumInts(5, 5)sau đó đã thực hiện một số tính toán và trả lại một giá trị cho người gọi.

Nếu bạn thử điều này với sumInts(4, 5), đây là những gì sẽ xảy ra:

• sumInts(4, 5)cố gắng trở về 4 + sumInts(5, 5). Để làm điều đó, nó gọi sumInts(5, 5).
  • sumInts(5, 5)cố gắng trở về 5 + sumInts(6, 5). Để làm điều đó, nó gọi sumInts(6, 5).
  • sumInts(6, 5)trả về 0 trở lại sumInts(5, 5).</li> <li>sumInts (5, 5) now has a value forsumInts (6, 5) , namely 0. It then returns5 + 0 = 5`.
• sumInts(4, 5)bây giờ có một giá trị cho sumInts(5, 5), cụ thể là 5. Sau đó nó trả về 4 + 5 = 9.

Nói cách khác, giá trị được trả về được hình thành bằng cách tổng hợp từng giá trị một, mỗi lần lấy một giá trị được trả về bởi một lệnh gọi đệ quy cụ thể sumIntsvà thêm vào giá trị hiện tại của a. Khi đệ quy chạm đáy, cuộc gọi sâu nhất trả về 0. Tuy nhiên, giá trị đó không ngay lập tức thoát khỏi chuỗi cuộc gọi đệ quy; thay vào đó, nó chỉ trao lại giá trị cho lệnh gọi đệ quy một lớp phía trên nó. Theo cách đó, mỗi cuộc gọi đệ quy chỉ cần thêm một số nữa và trả lại số đó cao hơn trong chuỗi, kết thúc với tổng kết. Như một bài tập, hãy thử truy tìm nó sumInts(2, 5), đó là những gì bạn muốn bắt đầu.

Hi vọng điêu nay co ich!

Bạn đã có một số câu trả lời tốt ở đây cho đến nay, nhưng tôi sẽ thêm một câu trả lời khác.

Trước hết, tôi đã viết nhiều bài viết về các thuật toán đệ quy đơn giản mà bạn có thể thấy thú vị; xem

http://ericlippert.com/tag/recursion/

http://bloss.msdn.com/b/ericlippert/archive/tags/recursion/

Đó là những thứ tự mới nhất, vì vậy hãy bắt đầu từ phía dưới.

Thứ hai, cho đến nay tất cả các câu trả lời đã mô tả ngữ nghĩa đệ quy bằng cách xem xét kích hoạt chức năng . Mỗi cuộc gọi tạo ra một kích hoạt mới và cuộc gọi đệ quy sẽ thực hiện trong bối cảnh kích hoạt này. Đó là một cách tốt để nghĩ về nó, nhưng có một cách khác, tương đương: seach-and-thay thế văn bản thông minh .

Hãy để tôi viết lại chức năng của bạn thành một hình thức nhỏ gọn hơn một chút; đừng nghĩ về điều này như trong bất kỳ ngôn ngữ cụ thể nào.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

Tôi hy vọng điều đó đúng. Nếu bạn không quen thuộc với toán tử có điều kiện, nó có dạng condition ? consequence : alternativevà ý nghĩa của nó sẽ trở nên rõ ràng.

Bây giờ chúng tôi muốn đánh giá s(2,5) Chúng tôi làm như vậy bằng cách thực hiện thay thế văn bản cuộc gọi bằng thân hàm, sau đó thay thế abằng 2và bbằng 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

Bây giờ đánh giá điều kiện. Chúng tôi thay thế bằng văn bản 2 > 5với false.

---> false ? 0 : 2 + s(2 + 1, 5)

Bây giờ văn bản thay thế tất cả các điều kiện sai bằng thay thế và tất cả các điều kiện đúng với hậu quả. Chúng tôi chỉ có điều kiện sai, vì vậy chúng tôi thay thế văn bản biểu thức đó bằng thay thế:

---> 2 + s(2 + 1, 5)

Bây giờ, để tiết kiệm cho tôi, tôi phải nhập tất cả các +dấu hiệu đó, thay thế bằng số học với giá trị của nó. (Đây là một chút gian lận, nhưng tôi không muốn phải theo dõi tất cả các dấu ngoặc đơn!)

---> 2 + s(3, 5)

Bây giờ tìm kiếm và thay thế, lần này với phần thân cho cuộc gọi, 3cho avà 5cho b. Chúng tôi sẽ đặt thay thế cho cuộc gọi trong ngoặc đơn:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

Và bây giờ chúng ta tiếp tục thực hiện các bước thay thế văn bản tương tự:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

Tất cả chúng tôi đã làm ở đây chỉ là thay thế văn bản đơn giản . Thực sự tôi không nên thay thế "3" cho "2 + 1" và cứ thế cho đến khi tôi phải làm thế, nhưng về mặt sư phạm, nó sẽ trở nên khó đọc.

Kích hoạt chức năng không gì khác hơn là thay thế lời gọi hàm bằng phần thân của cuộc gọi và thay thế các tham số chính thức bằng các đối số tương ứng của chúng. Bạn phải cẩn thận về việc giới thiệu dấu ngoặc đơn một cách thông minh, nhưng ngoài ra, đó chỉ là thay thế văn bản.

Tất nhiên, hầu hết các ngôn ngữ không thực sự thực hiện kích hoạt để thay thế văn bản, nhưng logic đó là nó là gì.

Vì vậy, một đệ quy không giới hạn là gì? Một đệ quy trong đó sự thay thế văn bản không dừng lại! Lưu ý rằng cuối cùng chúng ta đã đến một bước mà không còn gì sđể thay thế, và sau đó chúng ta có thể chỉ cần áp dụng các quy tắc cho số học.

Cách mà tôi thường tìm ra cách một hàm đệ quy hoạt động là bằng cách nhìn vào trường hợp cơ sở và làm việc ngược lại. Đây là kỹ thuật được áp dụng cho chức năng này.

Đầu tiên là trường hợp cơ sở:

sumInts(6, 5) = 0

Sau đó, cuộc gọi ngay phía trên trong ngăn xếp cuộc gọi :

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

Sau đó, cuộc gọi ngay phía trên trong ngăn xếp cuộc gọi:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

Và như vậy:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

Và như vậy:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

Lưu ý rằng chúng tôi đã đến cuộc gọi ban đầu của chúng tôi với chức năng sumInts(2, 5) == 14

Thứ tự thực hiện các cuộc gọi này:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

Thứ tự mà các cuộc gọi này trả về:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

Lưu ý rằng chúng tôi đã đi đến kết luận về cách thức hoạt động của chức năng bằng cách truy tìm các cuộc gọi theo thứ tự mà chúng trả về .

Đệ quy. Trong đệ quy Khoa học Máy tính được trình bày chuyên sâu theo chủ đề của Finite Automata.

Ở dạng đơn giản nhất, nó là một tài liệu tham khảo. Ví dụ, nói rằng "xe của tôi là xe hơi" là một tuyên bố đệ quy. Vấn đề là tuyên bố là một đệ quy vô hạn trong đó nó sẽ không bao giờ kết thúc. Định nghĩa trong tuyên bố của một "chiếc xe" là nó là "chiếc xe" nên nó có thể được thay thế. Tuy nhiên, không có kết thúc vì trong trường hợp thay thế, nó vẫn trở thành "xe của tôi là xe hơi".

Điều này có thể khác nếu tuyên bố là "xe của tôi là xe uốn cong. Xe của tôi màu xanh." Trong trường hợp đó, sự thay thế trong tình huống thứ hai cho xe hơi có thể là "bentley" dẫn đến "bentley của tôi có màu xanh". Các loại thay thế này được giải thích một cách toán học trong Khoa học máy tính thông qua các ngữ pháp không ngữ cảnh .

Sự thay thế thực tế là một quy tắc sản xuất. Cho rằng tuyên bố được đại diện bởi S và chiếc xe đó là một biến có thể là "bentley", tuyên bố này có thể được xây dựng lại theo cách đệ quy.

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

Điều này có thể được xây dựng theo nhiều cách, vì mỗi |phương tiện có một sự lựa chọn. Scó thể được thay thế bởi bất kỳ một trong những lựa chọn đó và S luôn bắt đầu trống. Các εphương tiện để chấm dứt sản xuất. Cũng như Scó thể được thay thế, các biến khác cũng vậy (chỉ có một và nó làC sẽ đại diện cho "bentley").

Vì vậy, bắt đầu với Sviệc trống rỗng, và thay thế nó bằng lựa chọn đầu tiên "my"S Strở thành

"my"S

Svẫn có thể được thay thế vì nó đại diện cho một biến. Chúng tôi có thể chọn "của tôi" một lần nữa hoặc để kết thúc nó, nhưng hãy tiếp tục đưa ra tuyên bố ban đầu của chúng tôi. Chúng tôi chọn không gian có nghĩa Slà được thay thế bằng" "S

"my "S

Tiếp theo hãy chọn C

"my "CS

Và C chỉ có một lựa chọn để thay thế

"my bentley"S

Và không gian một lần nữa cho S

"my bentley "S

Và vân vân "my bentley is"S, "my bentley is "S, "my bentley is blue"S,"my bentley is blue" (thay thế S cho ε kết thúc sản xuất) và chúng tôi đã đệ quy được xây dựng tuyên bố của chúng tôi "bentley của tôi là màu xanh".

Hãy nghĩ về đệ quy như những sản phẩm và thay thế. Mỗi bước trong quy trình thay thế người tiền nhiệm của nó để tạo ra kết quả cuối cùng. Trong ví dụ chính xác về tổng đệ quy từ 2 đến 5, bạn kết thúc với việc sản xuất

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

Điều này trở thành

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

Tôi sẽ cho nó đi.

Thực hiện phương trình a + sumInts (a + 1, b), tôi sẽ chỉ ra cách trả lời cuối cùng là 14.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

Cho chúng tôi biết nếu bạn có bất kỳ câu hỏi thêm.

Đây là một ví dụ khác về các hàm đệ quy trong ví dụ sau.

Một người đàn ông vừa tốt nghiệp đại học.

t là lượng thời gian tính bằng năm.

Tổng số năm thực tế làm việc trước khi nghỉ hưu, có thể được tính như sau:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

Và nó chỉ đủ để làm phiền bất cứ ai, lol. ;-P

Một mẹo thực sự hay mà tôi đã gặp khi học và thực sự hiểu về đệ quy là dành một chút thời gian để học một ngôn ngữ không có bất kỳ hình thức vòng lặp nào khác ngoài việc đệ quy. Bằng cách đó, bạn sẽ có được cảm giác tuyệt vời về cách SỬ DỤNG đệ quy thông qua thực hành.

Tôi đã theo dõi http://www.htdp.org/ , cũng như là một hướng dẫn Scheme, cũng là một giới thiệu tuyệt vời về cách thiết kế các chương trình về mặt kiến ​​trúc và thiết kế.

Nhưng về cơ bản, bạn cần đầu tư một chút thời gian. Nếu không có 'nắm vững' về đệ quy các thuật toán nhất định, chẳng hạn như quay lui, sẽ luôn có vẻ 'khó' hoặc thậm chí là 'ma thuật' đối với bạn. Vì vậy, hãy kiên trì. : -D

Tôi hy vọng điều này có thể giúp ích, chúc bạn may mắn!

Bạn có thể quan tâm đến việc thực hiện các chức năng của Nisan và Schocken . Pdf được liên kết là một phần của khóa học trực tuyến miễn phí. Nó mô tả phần thứ hai của một triển khai máy ảo, trong đó sinh viên nên viết một trình biên dịch ngôn ngữ máy-ngôn ngữ-máy-ngôn ngữ. Việc thực hiện chức năng mà họ đề xuất có khả năng đệ quy vì nó dựa trên ngăn xếp.

Để giới thiệu cho bạn về cách thực hiện chức năng: Hãy xem xét mã máy ảo sau:

Nếu Swift biên dịch sang ngôn ngữ máy ảo này, thì khối mã Swift sau:

mult(a: 2, b: 3) - 4

sẽ biên dịch xuống

push constant 2  // Line 1
push constant 3  // Line 2
call mult        // Line 3
push constant 4  // Line 4
sub              // Line 5

Ngôn ngữ máy ảo được thiết kế xung quanh một ngăn xếp toàn cầu . push constant nđẩy một số nguyên lên ngăn xếp toàn cầu này.

Sau khi thực hiện các dòng 1 và 2, ngăn xếp trông như sau:

256:  2  // Argument 0
257:  3  // Argument 1

256và 257là địa chỉ bộ nhớ.

call mult đẩy số dòng trả về (3) lên ngăn xếp và phân bổ không gian cho các biến cục bộ của hàm.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  0  // local 0

... Và nó đi - đến nhãn function mult. Mã bên trong multđược thực thi. Kết quả của việc thực thi mã đó, chúng tôi tính toán sản phẩm của 2 và 3, được lưu trữ trong biến cục bộ thứ 0 của hàm.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0

Ngay trước khi returning từ mult, bạn sẽ nhận thấy dòng:

push local 0  // push result

Chúng tôi sẽ đẩy sản phẩm lên ngăn xếp.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0
260:  6  // product

Khi chúng tôi trở lại, điều sau đây xảy ra:

• Đưa giá trị cuối cùng trên ngăn xếp vào địa chỉ bộ nhớ của đối số 0 (256 trong trường hợp này). Đây là nơi thuận tiện nhất để đặt nó.
• Hủy bỏ mọi thứ trên ngăn xếp đến địa chỉ của đối số 0.
• Chuyển đến số dòng trả về (3 trong trường hợp này) và sau đó tiến lên.

Sau khi trở về, chúng tôi đã sẵn sàng để thực hiện dòng 4 và ngăn xếp của chúng tôi trông như thế này:

256:  6  // product that we just returned

Bây giờ chúng tôi đẩy 4 lên ngăn xếp.

256:  6
257:  4

sublà một chức năng nguyên thủy của ngôn ngữ máy ảo. Nó nhận hai đối số và trả về kết quả của nó trong địa chỉ thông thường: đối số thứ 0.

Bây giờ chúng tôi có

256:  2  // 6 - 4 = 2

Bây giờ bạn đã biết cách gọi hàm hoạt động, việc hiểu đệ quy hoạt động như thế nào là tương đối đơn giản. Không có phép thuật , chỉ là một chồng.

Tôi đã thực hiện sumIntschức năng của bạn trong ngôn ngữ máy ảo này:

function sumInts 0     // `0` means it has no local variables.
  label IF
    push argument 0
    push argument 1
    lte              
    if-goto ELSE_CASE
    push constant 0
    return
  label ELSE_CASE
    push constant 2
    push argument 0
    push constant 1
    add
    push argument 1
    call sumInts       // Line 15
    add                // Line 16
    return             // Line 17
// End of function

Bây giờ tôi sẽ gọi nó:

push constant 2
push constant 5
call sumInts           // Line 21

Mã thực thi và chúng ta đi đến điểm dừng nơi ltetrả về false. Đây là những gì ngăn xếp vào thời điểm này:

// First invocation
256:  2   // argument 0
257:  5   // argument 1
258:  21  // return line number
259:  2   // augend
// Second
260:  3   // argument 0
261:  5   // argument 1
262:  15  // return line number
263:  3   // augend
// Third
264:  4   // argument 0
265:  5   // argument 1
266:  15  // return line number
267:  4   // augend
// Fourth
268:  5   // argument 0
269:  5   // argument 1
270:  15  // return line number
271:  5   // augend
// Fifth
272:  6   // argument 0
273:  5   // argument 1
274:  15  // return line number
275:  0   // return value

Bây giờ hãy "thư giãn" đệ quy của chúng tôi. return0 và goto dòng 15 và tiến.

271:  5
272:  0

Dòng 16: add

271:  5

Dòng 17: return5 và goto dòng 15 và tiến.

267:  4
268:  5

Dòng 16: add

267:  9

Dòng 17: return9 và goto dòng 15 và tiến.

263:  3
264:  9

Dòng 16: add

263:  12

Dòng 17: return12 và goto dòng 15 và tiến.

259:  2
260:  12

Dòng 16: add

259:  14

Dòng 17: return14 và goto dòng 21 và trước.

256:  14

Có bạn có nó. Đệ quy: Vinh quang goto.

Tôi nghĩ rằng cách tốt nhất để hiểu các hàm đệ quy là nhận ra rằng chúng được tạo ra để xử lý các cấu trúc dữ liệu đệ quy. Nhưng trong hàm ban đầu của bạn sumInts(a: Int, b: Int)tính toán đệ quy tổng các số từ ađến b, có vẻ như đó không phải là cấu trúc dữ liệu đệ quy ... Hãy thử một phiên bản sửa đổi một chút sumInts(a: Int, n: Int)trong đó nbạn sẽ thêm bao nhiêu số.

Bây giờ, sumInts được đệ quy trên n, một số tự nhiên. Vẫn không phải là dữ liệu đệ quy, phải không? Chà, một số tự nhiên có thể được coi là một cấu trúc dữ liệu đệ quy sử dụng các tiên đề Peano:

enum Natural = {
    case Zero
    case Successor(Natural)
}

Vì vậy, 0 = Zero, 1 = Succesor (Zero), 2 = Succesor (Succesor (Zero)), v.v.

Khi bạn có cấu trúc dữ liệu đệ quy, bạn có mẫu cho hàm. Đối với mỗi trường hợp không đệ quy, bạn có thể tính giá trị trực tiếp. Đối với các trường hợp đệ quy, bạn giả sử rằng hàm đệ quy đã hoạt động và sử dụng nó để tính toán trường hợp, nhưng giải cấu trúc đối số. Trong trường hợp của Natural, điều đó có nghĩa là thay vì Succesor(n)chúng ta sẽ sử dụng n, hoặc tương đương, thay vì nchúng ta sẽ sử dụng n - 1.

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

Bây giờ chức năng đệ quy đơn giản hơn để lập trình. Đầu tiên, trường hợp cơ sở n=0,. Chúng tôi nên trả lại những gì nếu chúng tôi muốn thêm không có số? Câu trả lời là, tất nhiên là 0.

Còn trường hợp đệ quy thì sao? Nếu chúng ta muốn thêm nsố bắt đầu bằng avà chúng ta đã có một sumIntschức năng làm việc cho n-1? Vâng, chúng ta cần thêm avà sau đó gọi sumIntsvới a + 1, vì vậy chúng tôi kết thúc với:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

Điều tốt đẹp là bây giờ bạn không cần phải suy nghĩ ở mức độ đệ quy thấp. Bạn chỉ cần xác minh rằng:

• Đối với các trường hợp cơ sở của dữ liệu đệ quy, nó sẽ tính toán câu trả lời mà không sử dụng đệ quy.
• Đối với các trường hợp đệ quy của dữ liệu đệ quy, nó tính toán câu trả lời bằng cách sử dụng đệ quy trên dữ liệu bị phá hủy.

Hãy suy nghĩ đệ quy như nhiều bản sao làm cùng một việc ...

Bạn yêu cầu sao chép [1]: "tổng số từ 2 đến 5"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

và Voila!!

Một chút lạc đề, tôi biết, nhưng ... hãy thử tra cứu đệ quy trong Google ... Bạn sẽ thấy ví dụ về ý nghĩa của nó :-)

Các phiên bản trước của Google đã trả về văn bản sau (được trích dẫn từ bộ nhớ):

Đệ quy

Xem đệ quy

Vào ngày 10 tháng 9 năm 2014, trò đùa về đệ quy đã được cập nhật:

Đệ quy

Ý bạn là: Đệ quy

Đối với câu trả lời khác, xem câu trả lời này .

Đã có rất nhiều câu trả lời hay. Tôi vẫn đang thử.
Khi được gọi, một hàm sẽ có một không gian bộ nhớ được phân bổ, được xếp chồng lên không gian bộ nhớ của hàm người gọi. Trong không gian bộ nhớ này, hàm giữ các tham số được truyền cho nó, các biến và giá trị của chúng. Không gian bộ nhớ này biến mất cùng với lệnh gọi kết thúc của hàm. Theo ý tưởng của ngăn xếp, không gian bộ nhớ của chức năng người gọi bây giờ sẽ hoạt động.

Đối với các cuộc gọi đệ quy, cùng một chức năng sẽ có nhiều không gian bộ nhớ được xếp chồng lên nhau. Đó là tất cả. Ý tưởng đơn giản về cách stack hoạt động trong bộ nhớ của máy tính sẽ giúp bạn thông qua ý tưởng về cách thức đệ quy xảy ra trong quá trình thực hiện.

Đệ quy bắt đầu có ý nghĩa với tôi khi tôi ngừng đọc những gì người khác nói về nó hoặc xem nó là điều tôi có thể tránh và chỉ viết mã. Tôi tìm thấy một vấn đề với một giải pháp và cố gắng sao chép giải pháp mà không cần tìm kiếm. Tôi chỉ nhìn vào giải pháp khi tôi bị mắc kẹt trong vô vọng. Sau đó tôi quay lại cố gắng nhân đôi nó. Tôi đã làm điều này một lần nữa trên nhiều vấn đề cho đến khi tôi phát triển sự hiểu biết và ý thức của riêng mình về cách xác định một vấn đề đệ quy và giải quyết nó. Khi tôi đạt đến cấp độ này, tôi bắt đầu giải quyết vấn đề và giải quyết chúng. Điều đó đã giúp tôi nhiều hơn. Đôi khi, mọi thứ chỉ có thể được học bằng cách tự mình thử và đấu tranh; cho đến khi bạn nhận được nó.