Hướng dẫn Khử một số dạng đệ quy

[dammage]

Tut của bạn programmer2010 viết bên forum cũ, bạn này hình như bỏ vn-zoom khá lâu rồi, thấy còn giá trị nên tui đem qua đây

Khử đệ quy cho 1 số dạng hàm

​

Yêu cầu tiên quyết: (Requisite) Khai báo và sử dụng được hàm trong C/C++. Hiểu được khái niệm đệ quy và viết được chương trình đệ quy.

Ngôn ngữ: C/C++. Có sử dụng cấu trúc của C++, nhưng có thể cài đặt dễ dàng trong C.

Mục tiêu: Nắm được cách khử đệ quy tuyến tính, nhị phân để giải quyết trường hợp đệ quy phi tuyến.


Mỗi chương trình có một vùng nhớ riêng đặc biệt gọi là stack, một cấu trúc "Last In First Out", hay "vào trước, ra sau". Cấu trúc Stack có hai thao tác chính: Đẩy vào đỉnh stack (Push) và Lấy ra từ đỉnh stack (Pop). Khi gọi hàm, các tham số được hàm gọi (caller) đẩy hết lên stack ngược với thứ tự xuất hiện của chúng, cuối cùng là địa chỉ của câu lệnh tiếp theo sau lời gọi để quay trở về.

Ngoài ra, các biến tạm (không static) của hàm cũng được lưu trữ trong stack. Ngay sau khi hàm được gọi (callee) khởi chạy, chính nó sẽ dành chỗ cho những biến này (bằng lệnh máy) và trả lại phần stack đó trước khi trả quyền điều khiển cho caller.

Nếu callee không phải void thì callee sẽ đẩy giá trị trả về vào stack cho caller. Dù gì thì dọn stack vẫn là nhiệm vụ của caller, sau đó nó sẽ tiếp tục chạy.

void caller() {
   //đẩy x,y,z lên stack
   //đẩy địa chỉ trở về lên stack
   callee(x,y,z)
   //dọn stack (x,y,z)
}

void callee(int t, int u, int v) {
   //dành chỗ cho biến nội
   // *sử dụng* t,u,v từ stack
   .......
   //thu lại vùng nhớ
   //lấy địa chỉ nhảy về từ stack và trả quyền điều khiển cho caller
}

Stack frame: (từ đỉnh xuống)
- Biến local của callee
- Địa chỉ trở về caller
- t,u,v (hay x,y,z)
- Biến local của caller
- Địa chỉ trở về caller trên nó
................................

Đệ quy tuyến tính​

# Một hàm đệ quy hay được đề cập là hàm tính giai thừa.

// code 1
uint64_t giaiThua(int32_t n) { return n<=0? 1 : giaiThua(n-1)*n; }

Đệ quy đuôi (tail recursion) nghĩa là hàm có lời gọi đệ quy là câu lệnh cuối cùng. Đây là trường hợp khử đệ quy dễ nhất vì máy không cần lưu trạng thái vào stack mà chỉ việc sửa lại tham số rồi "nhảy" trở lại phần đầu của hàm.

# Phân tích đoạn code hồi nãy thì thực sự phần đệ quy là:

int t = giaiThua(n-1)*n;
return t;

vậy đây không phải là dạng đệ quy đuôi. Để trở thành đệ quy đuôi thì thì bên lập trình hàm sẽ thêm một tham số lưu kết quả của bài toán lớn.

//code 2
uint64_t giaiThua(int32_t n, int64_t kq) {
   return n<=0 ? kq : giaiThua(n-1,kq*n);
}

// lời gọi: t = giaiThua(n,1);

Tất nhiên nhìn vào rất là chuối, nhưng từ đây dễ dàng viết ra 1 đoạn code tương đương như sau:

// code 3
uint64_t giaiThua(int32_t n) {
   uint64_t kq=1;
   while(n>0) { kq=kq*n; n=n-1; }
   return kq;
}

Vậy là ta khử được dạng đệ quy đuôi. Bây giờ ta sẽ qua dạng còn lại của đệ quy tuyến tính.

Vấn đề: In ngược danh sách liên kết (DSLK) đơn.

DSLK đơn là cấu trúc móc xích với mỗi mắt xích gồm dữ liệu (data) và một con trỏ đến mắt xích tiếp theo (next). Do DSLK đơn chỉ duyệt theo 1 chiều nên dữ liệu các node được đảo ngược ngầm qua tác động của stack.

// code 4
void inNguoc(Node* p) {
   if(p==NULL) return;
   inNguoc(p->next);
   print(p->data); //truy cập phần tử data trong node
}

Để khử đệ quy dạng này thì có thể nói cách duy nhất là tạo 1 stack riêng thay cho call stack của chương trình. Trong STL của C++ đã có cấu trúc std::stack với ba hàm quan trọng:
- push(value): đẩy vào
- pop(): lấy ra
- empty(): rỗng hay không rỗng.

Ta sẽ khai báo: std::stack<Node*> s;

Ở phần đầu ta thấy caller vừa đẩy tham số lên stack vừa dọn tham số ra khỏi stack. Hãy ghi nhớ kĩ điều này. Và khi stack này rỗng thì quá trình đệ quy của ta chấm dứt, nên ta sẽ cần vòng:
while(s.empty() != false) {

}

Dòng đầu tiên của "code 4" cho thấy rằng p==NULL là điều kiện dừng đệ quy. Và lời gọi đệ quy xảy ra ngay sau đó nên ta viết:
if(p!=NULL) { s.push(p->next); }
Đến đây ta phải nhìn thấy trước 1 bước. Sau khi gọi như vậy thì p của callee tức là p->next của caller. Vậy p phải trở thành p->next sau khi push.
if(p!=NULL) { s.push(p = p->next); }
Ta thấy rằng khi p==NULL thì không cần push nữa nên ta thay if(p!=NULL) bằng while(p!=NULL).

Trở lại hàm chính: callee nhận được tham số NULL và trả quyền cho caller. Lúc này ta phải dọn stack và xử lí nó. Vậy đoạn code làm việc này sẽ là:

//code 5a
if(s.empty()!=false) s.pop(); //lấy NULL ra trước
while(s.empty()!=false) {
   Node* t = s.pop();
   print(t->data);
}

Phần hoàn chỉnh code xin dành cho bạn đọc.

Tóm lại, điều ta cần nhớ là:
- Nếu không phải đệ quy đuôi thì ta biến đổi thành đệ quy đuôi HOẶC thay lời gọi đệ quy bằng lệnh push các tham số vào stack.
- Nếu sử dụng stack riêng thì ta xác định khi nào dừng đệ quy, sau đó xử lí dữ liệu và pop khỏi stack.
- Để biến đổi thành đệ quy đuôi thì hàm phải có dạng aggregate (tạm dịch là tổng hợp), hay bên lập trình hàm gọi là fold: r := fold(r, S, *) với S là dữ liệu, r là biến kết quả và *: S, r -> r. Đồng thời hàm nó biểu diễn phải có tính giao hoán thì mới đổi trực tiếp được.

Ví dụ như hàm tính giai thừa thì r là tích, S là số tự nhiên trong dãy và * là phép nhân. Nếu * là phép nhân ma trận thì do AB tính được chưa chắc BA tính được nên không thể đổi ra đệ quy đuôi. Phép tính trung bình không thể dùng đệ quy đuôi do không có chỗ cho N. avg: S -> fold(r, S, +)/|S|

Thực ra có thể sửa lại thành while(p!=NULL) { s.push(p); p=p->next; }. Khi đó DSLK rỗng <=> stack rỗng và lúc đó không có gì xảy ra.

Xong phần khử đệ quy tuyến tính.

 

[dammage]

Đệ quy nhị phân​

Cây nhị phân là một cấu trúc dữ liệu được cấu tạo từ nhiều node liên kết với nhau. Mỗi node có hai con trỏ left và right trỏ đến 0, 1 hay 2 node khác trong cây. Các node không trỏ đến node nào gọi là node lá.

Đến đây ta có thể định nghĩa được cây và cây con.
- Gốc cây là node mà từ node này ta đến được tất cả các node của cây. Mỗi cây có thể có đúng một node là gốc cây, hoặc rỗng.
- Cây con trái của một cây là cây có gốc được trỏ đến bởi con trỏ left của gốc cây lớn. Tương tự cho cây con phải.
- Độ sâu của cây là số node tối thiểu phải đi qua, đếm từ gốc cây, để đến được tất cả các node. Kí hiệu độ sâu cây root là depth(root) thì depth(NULL) := 0 và depth(root) := max(depth(root->left), depth(root->right)) + 1.

Ba thao tác duyệt cây: Duyệt cây có nghĩa là đi qua tất cả các node trong một cây. Có ba cách duyệt:

- Node-Left-Right (NLR): xử lí gốc cây trước sau đó duyệt cây con trái, rồi duyệt cây con phải.

void NLR(Node* root) {
   if(root==NULL) return; //cây rỗng
   process(root->data);
   NLR(root->left);
   NLR(root->right);
}

- Left-Node-Right (LNR)

void LNR(Node* root) {
   if(root==NULL) return;
   NLR(root->left);
   process(root->data);
   NLR(root->right);
}

- Left-Right-Node (LRN): Sau khi duyệt xong cả hai cây con thì mới quay lại gốc cây.

void LRN(Node* root) {
   if(root==NULL) return;
   LRN(root->left);
   LRN(root->right);
   process(root->data);
}

Rõ ràng việc duyệt cây k-phân (1-phân là DSLK rồi

) cần đến k lời gọi đệ quy trong một thể hiện (instance) của hàm. Ta sẽ đi vào từng ví dụ cụ thể cho mỗi dạng.

Dạng LNR: Tháp Hà Nội.

Bài Tháp Hà Nội được phát biểu như sau:

Cho n đĩa chồng lên nhau ở cột A sao cho đĩa nhỏ luôn nằm trên đĩa lớn. Với duy nhất cột B làm trung gian, hãy di chuyển cả n đĩa từ cột A qua cột C với ràng buộc: Vào bất kì thời điểm nào, đĩa nhỏ luôn nằm trên đĩa lớn.

Bài này có cả lời giải tuần tự cũng khá phức tạp, một lời giải bằng bit fiddling (thao tác bit) rất đáng nể và một lời giải đệ quy trông đơn giản, nhưng phải "giải nén" ra dần dần mới thực hiện được. Với cách nghĩ đệ quy, ta cố gắng quy bài toán chuyển n đĩa thành bài toán chuyển n-1 đĩa. Như vậy cột A chỉ còn mỗi chiếc đĩa to nhất. Rõ ràng ta không thể đặt ngay chồng n-1 đĩa lên cột C vì đặt lên rồi lại phải dỡ ra sao

nên nó phải nằm ở cột B và chiếc đĩa còn lại nằm ở C. Đánh số từ 1 đến n cho đĩa từ nhỏ đến lớn. Vậy thì:

Muốn chuyển n đĩa từ cột A sang cột C ta phải làm tuần tự:
- Chuyển n-1 đĩa từ A sang B
- Chuyển đĩa to nhất từ A sang C (thao tác cơ bản)
- Chuyển n-1 đĩa từ B sang C.

Để chuyển n-1 đĩa từ A sang B thì C phải là trung gian. Vậy ta viết được đoạn code sau:

void chuyen(int n, char A, char B, char C) {
   if(n<=0) return;
   chuyen(n-1,A,C,B);
   print(n-1,A,C);
   chuyen(n-1,B,A,C);
}

//khởi động: chuyen(n,'A','B','C');

Do có đến 4 tham số nên để thao tác được ta cần đên struct. Struct dùng để nhóm dữ liệu lại thành một khối (composition) và sau khi định nghĩa có thể khai báo như 1 kiểu bình thường (int, float...)


Trong bài này ta định nghĩa struct như sau:

typedef struct blob {
   int n;
   char A,B,C;
} blob;

void setto(blob*,int,char,char,char); //đưa dữ liệu vào blob
void getto(const blob*,int,char*,char*, char*) //lấy dữ liệu ra khỏi blob

và std::stack<blob> s;

Ta luôn giữ lại sườn hàm chuyen(int n, char A, char B, char C). Theo dõi luồng chạy thì lời gọi đệ quy đầu tiên có thể biến thành vòng lặp while. So sánh lời gọi đầu tiên với prototype: chuyen(n-1, A, C, B); thì ta cần phải đổi chỗ B, C như thế nào đấy. Có thể tránh push từ bên ngoài vòng lặp chính, nhưng khi đọc phải vận não để ra (A, C, B). Như vậy push xong rồi ta mới đổi chỗ B, C cho nhau.

while(n>0) { setto(b,n,A,B,C); s.push(b); swap(B,C); }

Lưu ý là n=1 vẫn phải push vì khúc sau ta sẽ pop ra đọc.

b = s.pop();
getto(&b,&n,&A,&B,&C);
print(n-1,A,C);

Giờ ta so lời gọi đệ quy thứ hai: chuyen(n-1, B, A, C); Vậy ta phải đổi chỗ A và B. Do đệ quy đuôi nên ta không cần phải đụng tới stack.

n = n-1;
swap(A,B);

Nếu stack rỗng thì toàn bộ những dòng từ s.pop(b) trở xuống không còn ý nghĩa gì, nên trước đó ta có: if(s.empty()) break;

Sau cùng úp 1 vòng do { } while(1); chung quanh là xong.

 

[dammage]

Dạng NLR: Quicksort.

Sort (Sắp xếp) là dời chỗ các phần tử trong mảng để tạo thành dãy có thứ tự nào đó. Thứ tự ở đây là dựa trên quan hệ thứ tự <, tức là:
- Với mọi a: a < a := FALSE.
- Với mọi a, b: a != b <=> a < b XOR b < a. [1][1bis]
- Với mọi a, b, c: a < b AND b < c => a < c.

Ý tưởng của Quicksort là chia mảng làm đôi: Chọn một phần tử chốt (pivot) a. Đổi chỗ như thế nào đó sao cho mảng có hai phần: một bên gồm các phần tử đều <= a và bên còn lại. Sắp xếp cả hai phần.

Ta chỉ cần thử QuickSort cho 0,1,2,3 phần tử là đủ thuyết phục

Và nó vẫn chia đều một dãy số toàn số 1.

void partition(T a[], int l, int r, int* i, int* j) {
// a[l..j] là đoạn "nhỏ" và a[i..r] là đoạn "lớn".
   T pivot = selectPivot(a,l,r);
   for(*i=l, *j=r; *i<=*j; ++*i, --*j) {
      while(a[*i] < pivot) ++*i;
      while(pivot < a[*j]) --*j;
      if(*i <= *j) swap(a[*i], a[*j]);
   }
}

void quickSort(T a[], int l, int r) {
   int i,j;
   if(r<=l) return;
   partition(a,l,r,&i,&j);
   quickSort(a,l,j); // (1)
   quickSort(a,i,r); // (2)
}

Tốc độ của thuật toán này phụ thuộc vào việc hàm partition có chia đều hay không, cũng chính là do hàm selectPivot() quyết định.

/!\ Do ta luôn thao tác trên mảng a nên không cần thiết phải lưu *a vào stack.

typedef blob { int l, r; } blob;

void setto(blob*,int,int);
void getto(const blob*,int*,int*);

Nếu ta cho pop() trước khi gọi partition() thì sẽ vướng lời gọi đệ quy đuôi (2). Vậy ta phải pop() ngay giữa (1) và (2). Và pop() chỗ này là chính xác vì khi dừng đệ quy thì caller chạy tiếp từ (2). Hay nói cách khác nếu r > l thì (2) mới chạy. Vậy ta viết được:

if(l<r) {
   partition(a,l,r,&i,&j);
   setto(b,l,j);
   s.push(b);
} else {
   b = s.pop();
   getto(...) //wut?
}

Xem lại lời gọi đệ quy thì nó là a(i,r) (!) mà r cũ ta không hề có. Do i phải bằng j+1 theo định nghĩa nên chỉ còn thiếu r. Vậy phải sửa lại là:
typedef blob { int l, r, old_r; } blob; tương tự cho getto và setto.

Vậy phần else sẽ trở thành:

 // ...
else {
   if(s.empty()) break;
   b = s.pop();
   getto(&b,&l,&r,&old_r);
   l=r+1; r = old_r;
}

-**********-​

Để giảm tác hại của việc chia không đều, một số đoạn code chọn lời gọi đệ quy lên đoạn lớn nhất làm lời gọi đệ quy đuôi, mà ta đã biết đệ quy đuôi không cần đến stack nên trong trường hợp xấu nhất stack sẽ ít bị phình ra hơn. Đoạn mã như sau:

void quickSort(T a[], int l, int r) {
   int i,j;
   if(r>=l) return;
   partition(a,l,r,&i,&j);
   if(j-l < r-i) {
      quickSort(a,l,j); quickSort(a,i,r);
   }
   else {
      quickSort(a,i,r); quickSort(a,l,j);
   }
}

Hãy khử đệ quy cho đoạn mã trên.

[1] Chỉ có một trong hai đúng. Nếu cả hai cùng sai hoặc cùng đúng thì ra FALSE.
[1bis] Ta có < chưa biết tính chất, nhưng != thì đã biết. Nếu a < a đúng thì mệnh đề bên phải sai, nhưng mệnh đề bên trái cũng sai, vậy nó không ràng buộc được trường hợp a==b.

-**********-​

Đến đây có thể thấy không phải hàm n tham số thì struct blob chỉ có n thành phần, mà ta cần phải quan tâm đến sự phụ thuộc giữa các lời gọi đệ quy.

 

[programmer2010]

/!\ Do ta luôn có tham số mảng là a nên ta chỉ cần lưu hai tham số là l và r.

Chỗ này giờ mới thấy nó kì kì "Do ta luôn thao tác trên mảng a nên không cần thiết phải lưu *a vào stack." nó hay hơn.

 

[programmer2010]

Thực ra tham số có thể truyền qua stack hay qua thanh ghi. Những hàm khử đệ quy trên truyền tham số qua các biến (đóng vai trò như "thanh ghi"), còn stack được dùng để lưu "thanh ghi" lại đến khi callee chạy xong.

Vậy thì với code Quicksort thì blob phải là{ int i, r; } chứ không phải như trên.

----------------------------------------------------------------

Ngay trước đoạn Quicksort thì có thêm:

Vị trí i, j là:

l.......j.....i..........r
<<<<<<<<=pivot=>>>>>>>>>>>

 

[programmer2010]

Khi mảng đủ nhỏ thì thời gian cho các lời gọi hàm Quicksort hay Merge Sort trở nên đáng kể so với các thao tác với bộ nhớ. Trong trường hợp này, Insertion Sort sẽ được sử dụng như sau:

if(r - l < THRESHOLD) insertionSort(a, r-l);
else ...

Vậy ta bổ sung như thế nào? Do r - l < THRESHOLD là điều kiện dừng đệ quy nên ta thay nó vào chỗ l < r. Vậy hàm insertionSort sẽ được gọi sau while.

while(1) {
   if(r - l >= THRESHOLD) {
      while(r - l >= THRESHOLD) {
         partition(a, l, r, &i, &j);
         getto(b, j, r);
         push(b);
      }
   }
   else //...
}

Ta có hai lựa chọn, hoặc lời gọi insertionSort sẽ nằm trong if, hoặc nó nằm trong else. Gọi ngay sau while là đúng, vì nó nằm ngay sau điều kiện; vả lại khi số lời gọi đệ quy trong thân hàm tăng lên thì sẽ phải có đúng bao nhiêu đó lời gọi vậy.

Nhưng như vậy hàm sẽ không làm gì cả nếu mảng ban đầu đã rất nhỏ. Vậy ta bỏ luôn câu if này và so sánh luồng chạy thì không có gì thay đổi. Câu if không cần thiết.

 

[programmer2010]

Dạng LRN: Merge Sort

Merge Sort dựa trên thao tác gộp hai mảng không tăng có kích thước bằng nhau thành một mảng không tăng. Việc này cần một mảng phụ có kích thước bằng với mảng a, nên prototype sẽ là

void _mergeArray(T[] source, int size1, int size2, T[] output);

Ta không cần xác định thêm mảng thứ hai vì hai mảng liền kề, tuy nhiên như vậy thì hàm này không nên gọi trực tiếp vì output[] không được cập nhật kích thước.

Như vậy code của hàm gộp sẽ là:

#include <cstring>

void _mergeArray(T[] source, int no1, int no2, T[] output) {
   T* source2 = source + size1; //do hai mảng liền kề.
   int i=0, j=0, idx=0;
   while(i < no1 && j < no2) {
      output[idx++] = source[i] > source2[j]?\ 
     source2[j++] : source[i++];
   }
   //Vì i, j tương ứng là số phần tử đã copy của source và source2.
   //memcpy(#1, #2, #3): copy #3 byte mem từ #2 qua #1.
   if(i < size1)
      memcpy(output+idx, source+i, (no1-i)*sizeof(T));
   else if(j < size2)
      memcpy(output+idx, source2+j, (no2-j)*sizeof(T));
}

Để tránh phải cấp phát động nhiều lần, ta hoán đổi vai trò giữa mảng phụ và mảng chính sau mỗi lần gộp mảng. Nếu không copy qua mảng phụ trước thì sẽ đến lúc mảng chính đóng vai trò output.

void mergeSort(T[] source, int size, T[] output) {
   if(n < THRESHOLD) {
      insertionSort(output, n);
   }
   else {
      mergeSort(output, size/2, source);
      mergeSort(output+size/2, size-size/2, source+size/2); //(1)
      _mergeArray(source, size/2, size-size/2, output); //(2)
   }
}

void sort(T[] a, int size) {
   //khởi tạo mảng temp như một bản sao của a.
   mergeSort(temp, size, a);
   free(temp);
}

Nhìn vào các tham số, ta tập trung vào output[], size và source[]. Nhưng còn một chi tiết nữa, ở đây có hai chỗ để trở về sau khi gọi. Thực ra hai hàm trước do có đệ quy đuôi nên không đặt ra vấn đề này. Vậy cấu trúc như sau:

typedef struct blob { T *output, *source; int size; int jump; } blob;
void setto(blob* b, T* output, T* source, int size, int jump);
void getto(const blob* b, T** output, T** source, int* size, int* jump);

Caller sẽ push "địa chỉ" của lệnh tiếp theo khi trở lại hàm.

Phần đầu cũng tương tự như bên LNR.

while(size > THRESHOLD) {
   setto(b, output, source, size, 1); //lời gọi thứ nhất
   s.push(b);
   swap(output, source);
   size = size/2;
}
insertionSort(output, size);

Ta đã có output, source, size và jump trên stack. Khảo sát lời gọi thứ hai, chỉ có size/2 xuất hiện nên không khó lắm.
Chú ý jump phải bằng 1.

s.pop(b);
getto(&b, &output, &source, &size, &jump);
if(jump == 1) {
   b.jump=2;
   s.push(b);
   //truyền tham số
   swap(output, source);
   output+=size/2; source+=size/2; size-=size/2; //đây là tham số hình thức.
}

Trở về từ lời gọi thứ hai.

else if(jump == 2) {
   _mergeArray(source, size/2, size-size/2, output);
   //???
}

Ba tham số vẫn không thay đổi, nên ta phải làm gì đây? Ngoài cách buộc phải pop trước mỗi lần lặp, còn có thể cắm flag để buộc phải reset, vì pop tại đây là không đúng do nó phải thực hiện sau vòng while.

Hết phần LRN.

 

[programmer2010]

Mình đi hơi nhanh quá nhỉ.