Đệ qui

Khái niệm

Các chương trình mà chúng ta đã xem xét đều có chung cấu trúc dạng hàm gọi các hàm khác dưới dạng mô hình phân cấp. Tuy nhiên đối với một số bài toán, việc dùng hàm gọi ngay chính nó rất hữu dụng. Có thể định nghĩa hàm đệ qui là hàm sẽ gọi đến chính nó trực tiếp hay gián tiếp thông qua các hàm khác. Vấn đề đệ qui là một vấn đề rất phức tạp, là chủ đề của nhiều khoá học nâng cao trong tin học, vì vậy trong phần này chỉ giới thiệu những khía cạnh cùng với những ví dụ đơn giản nhất của vấn đề đệ qui.

Trước tiên ta xem xét khái niệm đệ qui, sau đó kiểm tra trên một vài chương trình có chứa các hàm đệ qui. Cách tiến hành giải một bài toán đệ qui nhìn chung có những điểm chung sau.

Trước tiên gọi hàm đệ qui để giải bài toán, hàm đệ qui thực ra chỉ biết cách giải bài toán trong trường hợp đơn giản nhất (hay còn gọi là trường hợp cơ sở). Nếu hàm đệ qui được gọi trong trường hợp cơ sở, hàm chỉ cần đơn giản trả lại kết quả. Nếu hàm được gọi trong các trường hợp phức tạp hơn, hàm đệ qui sẽ chia công việc cần giải quyết thành hai phần. Một phần hàm biết cách giải quyết như thế nào, còn phần kia vẫn không biết cách giải quyết như thế nào tuy nhiên để được gọi là có khả năng đệ qui, phần sau phải giống với bài toán ban đầu nhưng đơn giản hơn hay nhỏ hơn bài toán ban đầu. Bởi vì bài toán mới giống với bài toán ban đầu nên hàm sẽ thực hiện gọi chính nó để giải quyết công việc đơn giản hơn này - đây chính là lời gọi đệ qui hay còn gọi là một bước đệ qui. Ðể đảm bảo việc đệ qui có kết thúc, mỗi một lần gọi đệ qui thì bài toán phải đảm bảo đơn giản hơn và các bước đệ qui này còn thực hiện tiếp cho dến khi nào bài toán đơn giản dần, đơn giản tới mức trở thành trường hợp cơ sở. Có thể nhận thấy hàm đệ qui xử lý trường hợp cơ sở để trả lại kết quả tính được cho các hàm mức phức tạp hơn, rồi đến lượt các hàm này lại tính trả lại kết quả cho các hàm phức tạp hơn nữa ... cứ như vậy cho đến lời gọi hàm ban đầu.

Ví dụ minh họa

Mới nghe có vẻ lạ lùng khi so sánh với cách giải quyết các bài toán thông thường. Nhưng trước khi nhận xét tiếp ta xem xét ví dụ tính n giai thừa ( n! ).

Theo định nghĩa n! bằng tích của tất cả các số tự nhiên từ 1 đến n:

n! = n* (n-1) ... 2 * 1

Ví dụ 5! = 5 * 4 * 3 * 2 * 1 = 120, 0! được định nghĩa bằng 1.

Ðể tính n! có thể dùng vòng lặp như sau :

factorial = 1;

for (i = n; i >= 1; i--)

factorial *= i;

Tuy nhiên cũng có thể định nghĩa đệ qui hàm giai thừa như sau :

Nếu n>0 n! = n * (n-1)!

Nếu n=0 n! = 0! = 1

Khi đó để tính 3! quá trình tính phải lần ngược trở về tính 0!, sau đó lấy kết quả để tính 1!, lại lấy kết quả để tính 2! và cuối cùng mới tính được 3! :

3! = 3*(2!) = 3*(2*(1!)) = 3*(2*(1*(0!)))

3! = 3*(2*(1*1))) = 3*(2*1) = 3*2 = 6

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

/* Tính giai thừa theo phương pháp đệ qui */

using System;

class Factorial

{

static long factorial( long number)

{

if ( number = 0 )

return 1;

else

return (number*factorial(number-1));

}

static void Main()

{

int i;

for ( i=0; i<=10; i=i+2)

Console.Write(“{0}! = {1} ", i, factorial(i));

}

}

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

Kết quả

0! = 1

2! = 2

4! = 24

6! = 720

8! = 40320

10! = 3628800

Chương trình trên : Tính giai thừa theo phương pháp đệ qui

Một ví dụ thứ hai dùng đệ qui là tính dãy số Fibonaci

Dãy số Fibonaci gồm những số 0, 1, 1, 2, 3, 5, 8, 13, 21 ...

bắt đầu từ hai số 0 và 1, tiếp sau đó các số Fibonaci sau bằng tổng của 2 số Fibonaci trước nó. Dẫy Fibonaci gặp rất nhiều trong thực tế, đặc biệt khi mô tả các mô hình xoắn ốc. Tỉ số giữa 2 số Fibonaci liên tiếp khoảng 1,618... Số này gặp rất nhiều trong thực tế và được gọi là tỉ số vàng. Các kiến trúc sư thường thiết kế kích thước cửa sổ, phòng, nhà ở có tỉ lệ giữa chiều dài và chiều rộng bằng tỉ số vàng. Các bưu thiếp cũng thường có tỉ lệ giữa chiều dài và chiều rộng bằng tỉ số vàng. Dẫy Fibonaci có thể định nghĩa đệ qui như sau:

fibonaci(0) = 0; fibonaci(1) = 1;

fibonaci(n) = fibonaci(n-1) + fibonaci(n-2) (n>1 Chương trình trong hình dưới đây tính đệ qui số Fibonaci thứ i bằng cách dùng hàm fibonaci. Chú ý rằng dãy số Fibonaci tăng rất nhanh, vì vậy chúng ta chọn kiểu long cho tham số và giá trị trả về của hàm fibonaci.

/* Tính dãy số Fibonaci phương pháp đệ qui */

using System;

class Fibonaci

{

static long fibonaci( long n)

{

if ( n = 0 || n = 1 )

return n;

else

return fibonaci(n-1) + fibonaci(n-2);

}

static void Main()

{

long result, number;

Console.Write("Hãy nhập vào một số nguyên : ");

number=long.Parse(Console.ReadLine());

result = fibonaci(number);

Console.Write("Fibonaci thứ {0} là : {1} ", number, result);

Console.Readkey();

}

}

Kết quả

Hãy nhập vào một số nguyên : 0

Fibonaci thứ 0 là : 0

Hãy nhập vào một số nguyên : 1

Fibonaci thứ 1 là : 1

Hãy nhập vào một số nguyên : 2

Fibonaci thứ 2 là : 1

Hãy nhập vào một số nguyên : 3

Fibonaci thứ 3 là : 2

Hãy nhập vào một số nguyên : 4

Fibonaci thứ 4 là : 3

Hãy nhập vào một số nguyên : 5

Fibonaci thứ 5 là : 5

Hãy nhập vào một số nguyên : 6

Fibonaci thứ 8 là : 8

Hãy nhập vào một số nguyên : 10

Fibonaci thứ 10 là : 55

Hãy nhập vào một số nguyên : 20

Fibonaci thứ 20 là : 6765

Hãy nhập vào một số nguyên : 35

Fibonaci thứ 35 là : 9227465

Chương trình trên:Tạo ra các số Fibonaci bằng đệ qui. Mỗi một lần hàm fibonaci được gọi, nó kiểm tra ngay lập tức xem liệu đây có phải là trường hợp cơ sở, n bằng 0 hay 1 hay không. Nếu đúng n được trả lại, bằng không, tức là khi n>1, nó sẽ tạo ra hai lời gọi đệ qui đơn giản hơn lời gọi đến hàm fibonaci ban đầu.

So sánh đệ qui và lặp

Ta đã xem xét cách tính giai thừa của một số, có thể tính theo phương pháp lặp (phi đệ qui) hoặc phương pháp đệ qui. Trong phần này ta sẽ so sánh hai phương pháp này và tìm hiểu tại sao trong thực tế thường chọn phương pháp lặp hơn. Lập trình đệ qui sử dụng cấu trúc lựa chọn, còn lặp sử dụng cấu trúc lặp. Cả hai phương pháp đều liên quan đến quá trình lặp, tuy nhiên phương pháp lặp sử dụng vòng lặp tường minh, còn phương pháp đệ qui có được quá trình lặp bằng các sử dụng liên tục các lời gọi hàm. Cả hai phương pháp đều phải kiểm tra khi nào thì kết thúc. Phương pháp lặp kết thúc khi điều kiện để tiếp tục vòng lặp sai, còn phương pháp đệ qui kết thúc khi đến trường hợp cơ sở, lặp thay đổi biến đếm trong vòng lặp cho đến khi nó làm cho điều kiện lặp sai còn đệ qui làm cho các lời gọi hàm đơn giản dần cho đến khi đơn giản tới trường hợp cơ sở. Cả hai phương pháp đều có thể dẫn đến trường hợp chạy vô hạn mãi, lặp sẽ không thoát ra được khi điều kiện lặp không bao giờ sai còn đệ qui không thoát ra được khi các bước đệ qui không làm cho bài toán đơn giản hơn và cuối cùng hội tụ về trường hợp cơ sở. Tuy nhiên đệ qui tồi hơn, nó liên tục đưa ra các lời gọi hàm làm tốn thời gian xử lý của bộ vi xử lý và không gian nhớ. Mỗi lần gọi hàm, lại cần thêm một bản sao của hàm, tốn thêm bộ nhớ (lưu các biến của hàm, địa chỉ trở về của hàm ...). Vì vậy phương pháp lặp được chuộng hơn. Tuy nhiên tồn tại nhiều bài toán chỉ có thể giải bằbg đệ qui.

Các bài toán có thể dùng Ðệ Qui

Thường áp dụng cho các bài toán phụ thuộc tham số có hai đặc điểm sau: Bài toán dễ dàng giải quyết trong một số trường hợp riêng ứng với các giá trị đặc biệt của tham số. Ta gọi đây là trường hợp suy biến. Trong trường hợp tổng quát, bài toán có thể qui về một bài toán cùng

dạng nhưng giá trị tham số thì bị thay đổi. Và sau một số hữu hạn bước biến đổi Ðệ Qui sẽ dẫn đến trường hợp suy biến. Nhận xét: Bài toán tính n! ở trên thể hiện rất rõ các đặc điểm này.

Cách xây dựng hàm Ðệ Qui

Hàm Ðệ Qui thường được viết theo thuật toán sau:

if ( trường hợp suy biến)

{

trình bầy cách giải bài toán

(giả định đã có cách giải)

}

else /* trường hợp tổng quát*/

{

gọi đệ qui tới hàm (đang lập) với

giá trị khác của tham số

}

Bài tập minh hoạ

B1

Viết hàm đệ qui để tính tổng sau:

S=1+2+3+...+n

/*Chương tình tính tổng S bằng hàm đệ qui*/

using System;

class TinhTong

{

static int tongs(int n)

{

if (n==1)

return 1;

else

return n+tong(n-1);

}

static void Main()

{

int n;

Console.Write("Nhap vao so n de tinh tong: ");

n=int.Parse(Console.ReadLine());

/*In ra ket qua */

Console.Write(" Tong S:={0}",tongs(n));

}

}

B2

/*Chương trình minh họa tìm ước số chung lớn nhất bằng phương pháp đệ qui*/

using System;

class Uscln

{

static int uscln(int n,int m)

{

int r;

r=n-m;

if (r==0)

return m;

else

return uscln(m,r);

}

static void Main()

{

int so1,so2;

Console.Write("Nhap so thu nhat:");

so1=int.Parse(Console.ReadLine());

Console.Write("Nhap so thu hai :");

so2=int.Parse(Console.ReadLine());

Console.Write("USCLN la {0}",uscln(so1,so2));

Console.ReadKey();

}

}