Lớp các bài toán giải được bằng đệ qui

Các ví dụ

nếu a = b thì UCLN = a

nếu a > b thì UCLN(a, b) = UCLN(a-b, b)

nếu a < b thì UCLN(a, b) = UCLN(a, b-a)

Từ đó ta có chương trình đệ qui để tính UCLN của a và b như sau.

int UCLN(int a, int b) // qui uoc a, b > 0

{

if (a < b) UCLN(a, b-a);

if (a > b) UCLN(a-b, b);

}

: Tính số hạng thứ n của dãy Fibonaci là dãy f(n) được định nghĩa:

f(n) = f(n-1) + f(n-2) với "n ³ 2.

{

long kq;

return kq;

}
: Chuyển tháp là bài toán cổ nổi tiếng, nội dung như sau: Cho một tháp n tầng, đang xếp tại vị trí 1. Yêu cầu bài toán là hãy chuyển toàn bộ tháp sang vị trí 2 (cho phép sử dụng vị trí trung gian 3) theo các điều kiện sau đây

mỗi lần chỉ được chuyển một tầng trên cùng của tháp,

tại bất kỳ thời điểm tại cả 3 vị trí các tầng tháp lớn hơn phải nằm dưới các tầng tháp nhỏ hơn.

Bài toán chuyển tháp được minh hoạ bởi hình vẽ dưới đây.

Bài toán có thể được đặt ra tổng quát hơn như sau: chuyển tháp từ vị trí di đến vị trí den, trong đó di, den là các tham số có thể lấy giá trị là 1, 2, 3 thể hiện cho 3 vị trí. Đối với 2 vị trí di và den, dễ thấy vị trí trung gian (vị trí còn lại) sẽ là vị trí 6-di-den (vì di+den+tg = 1+2+3 = 6). Từ đó để chuyển tháp từ vị trí di đến vị trí den, ta có thể xây dựng một cách chuyển đệ qui như sau:

chuyển 1 tầng từ di sang tg,

chuyển n-1 tầng còn lại từ di sang den,

chuyển trả tầng tại vị trí tg về lại vị trí den

hiển nhiên nếu số tầng là 1 thì ta chỉ phải thực hiện một phép chuyển từ di sang den.

Mỗi lần chuyển 1 tầng từ vị trí i đến j ta kí hiệu i ® j. Chương trình sẽ nhập vào input là số tầng và in ra các bước chuyển theo kí hiệu trên.

Từ đó ta có thể xây dựng hàm đệ qui sau đây ;

void chuyen(int n, int di, int den) // n: số tầng, di, den: vị trí đi, đến

{

if (n==1) cout << di << " ® " << den << endl;

cout << di << "®" << 6-di-den << endl; // 1 tầng từ di qua trung gian

chuyen(n-1, di, den) ; // n-1 tầng từ di qua den

cout << 6-di-den << "®" den << endl; // 1 tầng từ tg về lại den

}

}
main()

int sotang ;

cout << "Số tầng = " ; cin >> sotang;

chuyen(sotang, 1, 2);

}

Ví dụ nếu số tầng bằng 3 thì chương trình in ra kết quả là dãy các phép chuyển sau đây:

có thể tính được số lần chuyển là 2ⁿ - 1 với n là số tầng.