Hỏi về đệ quy

Tran_Hai_Anh · July 7, 2022, 1:54pm

Đệ quy cơ bản thì mình cũng hiểu nó gọi chính bản thân mình và phải chạy xong một lượt rồi quay ngược về đầu nên rất tốn bộ nhớ. Nhưng ở đoạn code dưới thì biến k nó hoạt động như thế nào mà k luôn bằng 1.

void dequy(int count,int k, int t)
{
  count--;
  if (count>0)	
    {
      t=t+1;
      cout<<"T = "<<t<<endl;
      cout<<"count = "<<count<<endl;
      dequy(count,k,t);
      k=k+1;
      cout<<"K = "<<k<<endl;
    }
}

int main ()
{
  int n=5;
  int k=0;
  int t=0;
  dequy(n,k,t);
  return 0;
}

rogp10 · July 7, 2022, 1:58pm

Code trên là đệ quy tuyến tính mà giá trị k chỉ thay đổi sau lời gọi đệ quy nên lúc nào cũng in ra K = 1 thôi.

Tran_Hai_Anh · July 7, 2022, 2:27pm

Mấy cái phần đệ quy tuyến tính rồi đệ quy đuôi nó khó hiểu ghê.
Theo như mình hiểu thì dequy() trong vòng if chạy đến khi count <=0 nhưng ko mô tả được thằng k nó hoạt động ntn. Viết ra giấy vẫn ko rõ nó hoạt động ra làm sao, mà bình thường dùng đệ quy rất cơ bản, chả bao giờ dính thằng này. Mấy bữa nay làm về Merge Sort ngáo luôn phần đệ quy trộn mảng.

void mergeSort(int a[], int l, int h)
{

    if(l<h)
    {
        int m =  l+r/2,
        mergeSort(a,l,m);
        mergeSort(a,m+1,h);
        merge(a,l,m,h);  <-- 
    }
}

library · July 7, 2022, 11:12pm

Cậu đã nghe tới “pass by value” (truyền tham trị) bao giờ chưa?

Trong C/Cpp, hay rất nhiều ngôn ngữ khác, by default, sử dụng pass by value.
Biến k của cậu cũng được pass by value, tức là cậu chỉ truyền giá trị biến k chứa (hay cậu đã truyền vào 1 bản sao của biến k vào hàm), không phải truyền địa chỉ chính xác của biến k.
Vậy nên, bất cứ thay đổi gì trong hàm lên bản sao của biến k đều không ảnh hưởng tới biến k thực sự. Đó là lý do sau khi gọi đệ quy xong, cậu thấy biến k quay lại như cũ.
Lợi dụng đặc trưng đó mà cậu có cài đặt đệ quy như trên.

Hope it helps!

Vu_Nguyen5 · July 8, 2022, 3:51am

thêm mỗi 1 ký tự là chạy được, nhưng bạn nên tìm hiểu thêm tại sao lại thế

void dequy(int count,int &k, int t)

Tran_Hai_Anh · July 8, 2022, 4:54am

Mình cũng biết là có 3 kiểu truyền đối số là truyền giá trị, truyền địa chỉ và truyền tham chiếu cơ mà cả 2 biến t và k đều là truyền giá trị vào dequy(), sau mỗi lần gọi thì dequy() đều tạo t và k với những địa chỉ mới nhưng t gọi trước đệ quy thì nó vẫn tăng giá trị qua mỗi lần gọi còn k chỉ tăng duy nhất 1 lần rồi thôi.

Vu_Nguyen5 · July 9, 2022, 2:12am

biến t bạn tăng xong in ra rồi truyền vào hàm, còn biến k bạn chạy hàm xong mới tăng thì giá trị của k đâu có thay đổi đâu.

library · July 10, 2022, 7:07am

Uhm, cậu đã biết khái niệm đó thì tớ nghĩ cậu nên dễ dàng giải thích được hành vi của code này chứ?

Mình cũng biết là có 3 kiểu truyền đối số là truyền giá trị, truyền địa chỉ và truyền tham chiếu

Có 2 kiểu thôi cậu ạ. Truyền địa chỉ là truyền tham chiếu đó cậu

Ở code của cậu

      t=t+1; // phiên bản của biến t của hàm
      cout<<"T = "<<t<<endl; // in ra giá trị của phiên bản t của hàm
      cout<<"count = "<<count<<endl;
      dequy(count,k,t);
      k=k+1; // tăng giá trị của phiên bản của k của hàm lên 1 đơn vị
      cout<<"K = "<<k<<endl; // dù cậu gọi hàm dequy bao nhiêu phiên bản k của hàm vẫn không đổi, do cậu không sửa được giá trị của k với cách gọi của cậu

Tran_Hai_Anh · July 10, 2022, 9:53am

Nghĩa là t ở trước dequy() nên mỗi lần gọi đều dc cập nhật giá trị và lưu vào t có địa chỉ mới.

Còn k thì ở sau dequy(), và vì dequy() phải thực hiện đến khi kết thúc (không thỏa mãn điều kiện count>0 nữa) thì lúc đó dừng và thực hiện dòng sau là in ra k với n lần (n: số lần dequy() đã thực hiện).

Vẫn hơi lơ mơ nhưng mình hiểu thế này có đúng không nhỉ? Và nó phải in ra n lần "K = " (vì dequy() đã gọi n lần). Thằng t cũng không tham chiếu nhưng vì nó gọi trước dequy() nên nó vẫn truyền được giá trị cho các lần tính sau? Còn k gọi sau nên không truyền được giá trị?

Đang tìm kiếm mấy bài giảng về đệ quy nhưng đều đến hàm dequy() là dừng luôn, ko có gì đằng sau cần xử lý cả.

qloved · July 10, 2022, 10:10am

Có gì khó hiểu đâu nhỉ. Hiểu đơn giản thì đệ quy chính là quá trình gọi lại chính bản thân nó, khi nó gọi lại chính bản thân nó thì thực tế nó cũng giống như gọi 1 hàm bình thường khác. Tức là:

phạm vi của biến giống như hàm thông thường
giá trị truyền vào giống như hàm thông thường
giá trị trả về cũng giống như hàm thông thường

Lập tình đệ quy cũng tương tự như chứng minh quy nạp:

bắt đầu với case cơ bản (điều kiện dừng)
tiếp tục phát triển dựa trên case cơ bản (điều kiện lặp)

Điểm mấu chốt nhất ở đây là bạn phải nắm được phạm vi hoạt động của biến, từ đấy mới có thể hiểu được cặn kẽ vấn đề

Tran_Hai_Anh · July 10, 2022, 10:32am

Kiến thức kỳ quái này đã được tiếp thu.
Thông luôn cả mấy bài đệ quy trong thuật toán sắp xếp. Cảm ơn ae.

library · July 12, 2022, 5:54am

Cậu hiểu đúng rồi đấy