Bạn nên tiếp cận đệ quy như thế nào?

Question

Tôi hiện đang nghiên cứu đệ quy ở trường và tôi gặp khó khăn khi nghĩ về các phương pháp khi có nhiều cuộc gọi đệ quy. Tôi chỉ muốn hỏi làm thế nào bạn nên suy nghĩ về đệ quy bởi vì tôi biết truy tìm các cuộc gọi phương pháp theo từng bước sẽ trở nên quá tẻ nhạt.

Thay vì truy tìm từng cuộc gọi đệ quy, điều chúng tôi đã đề cập ngắn gọn là suy nghĩ về đệ quy bằng cảm ứng, nhưng vấn đề tôi gặp phải là cảm ứng có thể áp dụng cho các tình huống khác với toán học. Giống như nếu có một phương pháp mà đệ quy in ra số như thế này:

public void blah(int n) 
{ 
    for (int i = 0; i < n; i++) 
     blah(i); 
    System.out.print(n); 
} 

tôi gặp khó khăn khi suy nghĩ về những gì in ra, và tôi không thể nhìn thấy như thế nào cảm ứng có thể là liên quan ở đây (tha thứ ngu dốt của tôi nếu nó có thể được được sử dụng ở mọi nơi).

Nhưng tôi đoán câu hỏi thực sự của tôi là cách bạn có thể giải quyết đệ quy mà không phải theo dõi mọi cuộc gọi phương thức đơn lẻ? Là điều tốt nhất để làm chỉ để xem trường hợp cơ bản và loại công việc ngược? (Nhưng ngay cả sau đó tôi nghĩ rằng tôi nhận được mờ về những gì sẽ xảy ra).

Answer 1

cách bạn có thể giải quyết đệ quy mà không phải theo dõi mọi cuộc gọi phương thức đơn lẻ?

Có một số cách "hiểu" chương trình đệ quy - một cách liên quan đến suy nghĩ về cuộc gọi đệ quy dưới dạng hộp đen và hộp kia yêu cầu "phát" một vài trường hợp và đoán mẫu.

Phương pháp đầu tiên thừa nhận rằng phương pháp đệ quy đã được viết, và nó hiện một số điều được biết đến. Điều này rất hữu ích khi bạn nghĩ về các trình phân tích cú pháp gốc đệ quy; nó không phải là tốt cho các chương trình sản xuất đầu ra (như trái ngược với tốn đầu vào), chẳng hạn như bạn.

Phương pháp thứ hai áp dụng nhiều hơn cho các chương trình tương tự như ví dụ của bạn. Phát nội dung đó cho các giá trị 0, 1, 2 và 3.

0 - 0 
1 - 0 1 
2 - 0 0 1 2 
3 - 0 0 1 0 0 1 2 3 

Bạn có nhận thấy mẫu không? Đầu ra cho N liệt kê các kết quả đầu ra cho N-1 các mục trước và in N ở cuối. Một khi bạn nghĩ rằng bạn có thể tiếp tục các mô hình, bạn biết rằng bạn có một sự hiểu biết về chương trình đệ quy của bạn.

Answer 2

Bạn có thể tìm thấy một lời giải thích tốt đẹp về Suy nghĩ đệ quy trên here

Từ liên kết

• Viết một nguyên mẫu cho hàm đệ quy.

• Viết nhận xét mô tả chức năng của chức năng.

• Xác định trường hợp cơ sở (có thể có nhiều trường hợp) và các giải pháp của nó.

• Xác định vấn đề nhỏ hơn (hoặc vấn đề) cần giải quyết. Nếu nó làm cho nó dễ dàng hơn cho bạn để làm theo, tiết kiệm các giải pháp nhỏ hơn
  vấn đề để biến địa phương (ví dụ nhỏ trong sum() chẳng hạn) .ASSUME cuộc gọi đệ quy làm việc

• Sử dụng các giải pháp của vấn đề nhỏ hơn để giải quyết vấn đề lớn hơn. (Nếu điều này được thực hiện KHÔNG HOÀN THÀNH, các giải pháp của các vấn đề
  nhỏ hơn cũng sẽ được tính sai, do đó, giả định trong
  bước trước đó sẽ không thành công).

Answer 3

Đây là cách tôi nghĩ về đệ quy. Nó thực sự khá đơn giản.

• Tôi cần phải làm gì để dừng lại? Trường hợp này được gọi là trường hợp cơ sở của bạn.
• Tôi phải làm gì nếu chưa hoàn thành?

Lấy ví dụ, vấn đề đệ quy cổ điển: F (n) = n !. 0! được định nghĩa là 1 và bất kỳ điều gì khác lớn hơn 0 được xác định là n * F (n-1)

Trong ví dụ này, tôi đáp ứng hai điều kiện của mình - Tôi dừng lại khi tôi nhấn 0 !, giá trị tôi có bởi giá trị thứ (n-1).

Một cách tiếp cận tôi sử dụng: nếu nó có thể được thực hiện một cách đệ quy, sau đó nó có thể được thực hiện lặp đi lặp lại. Đây là để nói, nếu tôi có thể viết một vòng lặp để thực hiện nhiệm vụ tương tự, sau đó tôi có thể viết một phương thức đệ quy để thực hiện nhiệm vụ là tốt. Thường dễ dàng hơn để suy nghĩ về các vấn đề nhất định (ví dụ: Ackermann's Function) và các trường hợp khác theo cách lặp lại (ví dụ: đi bộ xuống danh sách được liên kết).

Bạn sẽ muốn sử dụng lặp nơi nó phù hợp với bạn nhất.

Answer 4

dụ của bạn sẽ in ra

0 0 1 0 0 1 2 0 0 1 0 0 1 2 3 4 

Nếu gọi với blah (4).

Nói chung khi recursing tôi chắc chắn rằng để xử lý các trường hợp cơ sở đầu tiên. Sau đó, xử lý trạng thái đệ quy, sau đó logic có thể đến.

Trong ví dụ này, sự kiểm soát trường hợp cơ sở là i < n và sẽ xảy ra đầu tiên tại 0 < 0 đó là không đúng sự thật và phá vỡ các vòng lặp for in ra 0. Sau đó, phiên bản kế tiếp ra sẽ chạy, mà là để đi từ i = 0 to 1 < 1 mà một lần nữa in ra 0 sau khi gọi i = 0 < 0. Sau đó, nó kết thúc vòng lặp và 1 được in. Sau đó là lượt 2s, lol. Và cứ tiếp tục xuống dòng cho đến khi mỗi số đã có lượt.

Answer 5

Không chắc chắn chính xác làm thế nào để cho bạn biết để nghĩ về nó nhưng tôi nghĩ rằng điều này có thể giúp bạn nắm bắt những gì mà dòng chảy trông như thế nào. Bạn có cảm giác về nó sau khi bạn mã hóa nó một lúc, nhưng rất nhiều người chỉ tránh nó bởi vì nó làm cho họ cảm thấy u ám. Tôi xin lỗi rằng nó không được mã hóa trong Java, nhưng nó không phải về mã của nó về những gì nó in vì vậy chỉ cần chạy nó trên bất kỳ hộp Linux hoặc Cygwin.

perl -e 'sub foo {my $n =shift;my $depth=shift;print "\t"x$depth;print "blah($n)\n";for(my $i=0;$i<$n;$i++){foo($i,$depth+1)};print "\t"x$depth;print $n,"\n"};foo(shift);' 5 

gọi với một arg 3 đây là những gì nó trông giống như:

blah(3) 
      blah(0) 
      0 
      blah(1) 
        blah(0) 
        0 
      1 
      blah(2) 
        blah(0) 
        0 
        blah(1) 
          blah(0) 
          0 
        1 
      2 
    3 

tôi cố gắng như người khác nói để hình dung nó trong thành phần nhỏ hơn. I E. Chức năng làm gì ngoài việc đệ quy.Trong trường hợp này hàm đếm từ 0 đến một số. Bây giờ yếu tố trong những gì đệ quy nào. Đối với mỗi lần đếm nó bắt đầu một số mới lên đến số nó đã đạt tới. Thường thì tôi thấy rằng nó giúp phá vỡ nó thành nhiều hơn một chức năng sao cho những gì nó thực sự làm được đóng gói, và đệ quy tách biệt, nhưng điều này làm cho đệ quy kém rõ ràng hơn.

Tôi nghĩ rằng nó cũng giúp sử dụng các vấn đề trong thế giới thực, chẳng hạn như duyệt qua hệ thống phân cấp thư mục hoặc cấu trúc cây khác.

Answer 6

Vì vậy, tôi sẽ là người cùn ở đây, bạn sẽ nhận được đệ quy hoặc bạn sẽ không và hoàn toàn không có gì sai với điều đó. Nó chỉ là một trong những thứ phân tách các lập trình viên (sad but true according to Joel). Bây giờ để giải thích đệ quy như bạn năm là nơi mà nhiệm vụ trở thành một chút u ám. Hãy tưởng tượng bạn có bốn (4) quả táo và mỗi lần tôi yêu cầu bạn đếm chúng bạn lấy một trong những quả táo của bạn và đưa nó cho tôi. Lần đầu tiên tôi nói chuyện với bạn, bạn sẽ cho tôi biết bạn có bốn quả táo và một tay cho tôi. Bây giờ chúng tôi tiếp tục quá trình này cho đến khi bạn không có quả táo này sẽ tương tự với những gì người khác đã gọi là base case hoặc exit statement để đảm bảo rằng chức năng của bạn sẽ chấm dứt.

Bây giờ, bạn không còn năm, nếu tôi yêu cầu bạn chứng minh rằng đối với tất cả các trường hợp N rằng điều này sẽ hoạt động như thế nào bạn sẽ làm điều đó? Đây là những gì giáo sư của bạn đang nhận được khi ông nói để giải quyết một vấn đề thông qua cảm ứng. Một ví dụ về cách giải quyết bằng cảm ứng sẽ như sau: Tôi có sáu lon Mountain Dew trên bàn làm việc của tôi và tôi đang trong quá trình uống một trong số chúng. Tôi nói "Wow có thể có mùi vị của Mountain Dew giống như cầu vồng điện." Tôi sẽ sử dụng cảm ứng để nói rằng năm lon khác và mở rộng tất cả lon của hương vị Mountain Dew như cầu vồng điện. Vì vậy, trong trường hợp đệ quy, bạn chứng minh rằng một hàm sẽ kết thúc và sử dụng đúng quy trình tương tự.

Nó có thể giúp giải quyết một trường hợp "tầm thường" của vấn đề như blah(0) and blah(1) and blah(2) điều này sẽ cho bạn thấy xu hướng giải pháp theo hướng bạn dự đoán cũng như thực tế bạn có thể sử dụng cảm ứng để nói rằng quá trình này sẽ chấm dứt mọi đầu vào N.