Đầu tiên, chúng ta hãy xem xét bài toán chứng minh sau: Chứng minh rằng đẳng thức dưới đây đúng với mọi số tự nhiên n:
1 + 3 + 5 + ⋯ + (2n-1) = n^2 (1)
Ở trình độ trung học cơ sở, chúng ta đã được học về phương pháp quy nạp toán học dùng để chứng minh một đẳng thức hoặc bất đẳng thức. Áp dụng phương pháp này, chúng ta có thể giải quyết bài toán trên một cách dễ dàng:
Bước 1: Chứng minh đẳng thức đúng với n=1: Ta thấy 1 = 1^2, do đó đẳng thức đúng với n=1.
Bước 2: Lập giả thiết quy nạp - Giả sử đẳng thức đúng với n=k≥1: Tức là ta có: 1 + 3 + 5 + ⋯ + (2k-1) = k^2 (2).
Bước 3: Ta chứng minh đẳng thức đúng với n=k+1, tức là cần chứng minh: 1 + 3 + 5 + ⋯ + (2k-1) + (2(k+1)-1) = (k+1)^2 (3).
Để chứng minh đẳng thức (3), chúng ta sẽ sử dụng giả thiết đẳng thức (2). Thực hiện các phép biến đổi:
Vậy, từ giả thiết đẳng thức (2), chúng ta đã chứng minh được đẳng thức (3) đúng với n=k+1.
Nhờ phương pháp quy nạp, chúng ta đã chứng minh được rằng đẳng thức (1) đúng với mọi số tự nhiên n.
II. Giải thuật đệ quy
Bài toán P được gọi là có tính chất đệ quy khi lời giải của nó có thể được chuyển thành lời giải của bài toán P' nhỏ hơn và có cùng cấu trúc với nó, đồng thời lời giải của P' không phụ thuộc vào P. Các lời giải cho những bài toán như vậy được gọi là giải thuật đệ quy. Bản chất của giải thuật đệ quy là phân tách một bài toán lớn thành các bài toán nhỏ hơn và dễ giải hơn, sau đó kết hợp các lời giải của các bài toán nhỏ lại để tạo thành lời giải cho bài toán lớn ban đầu. Bài toán tìm giai thừa của n là một ví dụ cơ bản cho các bài toán có tính chất đệ quy.
Quy nạp toán học và giải thuật đệ quy có mối quan hệ chặt chẽ: Trong quy nạp toán học, chúng ta chứng minh tính chất toán học bằng cách chứng minh rằng nó đúng với các trường hợp cơ sở sau đó dựa trên điều này chứng minh rằng nó đúng với mọi số tự nhiên n dựa trên việc nó đã đúng với các số tự nhiên nhỏ hơn n. Tương tự, trong giải thuật đệ quy, chúng ta tìm lời giải cho các bài toán cơ sở (thường rất đơn giản), sau đó cài đặt để lời giải của bài toán lớn được suy ra từ lời giải của các bài toán nhỏ hơn cùng cấu trúc.
III. Công thức truy hồi
Sau khi phân tách bài toán có tính chất đệ quy thành các bài toán nhỏ hơn, chúng ta có hai nhiệm vụ:
Tìm lời giải cho các bài toán cơ sở.
Kết hợp lời giải của các bài toán con thành lời giải cho bài toán lớn.
Bước thứ nhất thường đơn giản vì các bài toán cơ sở có kích thước nhỏ và dễ giải. Tuy nhiên, bước thứ hai đòi hỏi tư duy nhiều hơn. Công thức truy hồi được sử dụng để liên kết các bài toán nhỏ với bài toán lớn. Trong toán học, có nhiều định nghĩa về công thức truy hồi. Ví dụ:
Xác định công thức truy hồi của một bài toán đệ quy là quyết định quan trọng để có thể giải bài toán đó. Lời giải đệ quy có thể được thực hiện bằng cách cài đặt đệ quy hoặc cài đặt không đệ quy. Trên phần tiếp theo, chúng ta sẽ tìm hiểu cách cài đặt các hàm đệ quy để giải các bài toán có tính chất đệ quy.
IV. Hàm đệ quy và các thành phần của hàm đệ quy
1. Khái niệm về hàm đệ quy
Các lời giải đệ quy cho một bài toán có thể được ghi lại trong một hàm gọi là hàm đệ quy. Một hàm đệ quy có đặc điểm là luôn gọi lại chính nó (thực tế, bài toán đệ quy cũng là việc giải lại bài toán gốc nhưng với kích thước nhỏ hơn):
Một cách dễ hiểu nhất, chúng ta có thể tưởng tượng hàm đệ quy như một vòng lặp. Tương tự như vòng lặp, hàm đệ quy sẽ lặp lại việc thực hiện đoạn mã bên trong nó một số lần cụ thể. Tuy nhiên, khác với vòng lặp, hàm đệ quy gọi lại chính nó để thực hiện các lần lặp tiếp theo. Hàm đệ quy có thể được hiểu như một loại vòng lặp "tự thân" hoạt động bằng cách gọi lại chính nó để tiếp tục thực hiện các bước trong quá trình giải quyết bài toán.
2. Các thành phần của một hàm đệ quy
Một hàm đệ quy luôn bao gồm hai phần chính:
Phần cơ sở (base case): Đây là lời giải cho bài toán cơ sở, và đồng thời thể hiện tính dừng của thuật toán. Khi hàm đệ quy gọi lại chính nó tới một thời điểm nhất định, phần cơ sở sẽ được thực hiện. Phần cơ sở giải quyết bài toán một cách trực tiếp mà không cần phải dựa vào bất kỳ bài toán con nào. Nó thường là một phần rất đơn giản và đạt được kết quả trực tiếp.
Phần đệ quy (recursive part): Trong trường hợp bài toán không thể được giải bằng phần cơ sở, ta xác định các bài toán con và gọi đệ quy tới các bài toán con đó để giải chúng. Sau khi có lời giải của các bài toán con, ta sẽ kết hợp chúng lại bằng công thức truy hồi để có được lời giải cho bài toán gốc. Phần này thể hiện tính quy nạp của thuật toán, vì lời giải của bài toán gốc phụ thuộc vào lời giải của các bài toán con nhỏ hơn.
Tổng hợp hai phần này, hàm đệ quy sẽ tiến hành giải quyết bài toán thông qua việc giải quyết bài toán cơ sở hoặc gọi đệ quy tới các bài toán con, tùy thuộc vào tính dừng và tính quy nạp của thuật toán.
3. Cơ chế hoạt động của một hàm đệ quy
Ta lấy một ví dụ là hàm đệ quy tính n! như sau:
Vẫn còn nội dung phía dưới, bạn hãy ấn nút để xem tiếp nhé...
Ở bài toán này, phần cơ sở (base case) được định nghĩa như sau: khi n = 0, lời giải là 1. Đối với các bài toán có n > 1, ta sử dụng lời gọi đệ quy để giải bài toán có kích thước nhỏ hơn n - 1, sau đó tính giai thừa bằng công thức (n-1)! × n. Ví dụ, nếu chúng ta sử dụng hàm này để tính 3!, giải thuật sẽ diễn ra như sau:
Bước 1: Gọi hàm đệ quy để tính giai thừa của (3-1) = 2. (Đây là một bài toán con nhỏ hơn.)
Bước 2: Gọi hàm đệ quy để tính giai thừa của (2-1) = 1. (Đây là bài toán cơ sở, kết quả trực tiếp là 1.)
Bước 3: Kết hợp kết quả từ bước 2 và n = 3 theo công thức (2-1)! × 3 để tính toán giai thừa của 3.
Bước 4: Trả về kết quả giai thừa của 3.
Kết quả cuối cùng là 3!, tức là 6.
Thông qua lời gọi đệ quy và công thức truy hồi, chúng ta có thể tính được giai thừa của một số tự nhiên bất kỳ bằng cách chia bài toán thành các bài toán con nhỏ hơn và kết hợp lời giải của chúng lại để thu được lời giải cho bài toán gốc.
Việc giải bài toán factorial(3) sẽ diễn ra trong 6 bước từ việc phân rã factorial(3) xuống factorial(0) rồi lần lượt trả ngược kết quả các bài toán nhỏ lên các bài toán lớn hơn đã gọi nó, cho tới khi đạt được kết quả của bài toán ban đầu. Nguyên lý của việc này là khi máy tính gặp một lời gọi đệ quy chưa được giải, nó sẽ lưu tạm thời bài toán đó vào một ngăn xếp (stack) theo thứ tự từ trên xuống dưới. Do đó, các bài toán chưa được giải sẽ xếp chồng lên nhau theo thứ tự từ lớn đến nhỏ. Việc giải các bài toán được thực hiện từ trên xuống dưới, trong đó bài toán ở phía dưới (lớn hơn) sẽ nhận kết quả từ bài toán ở phía trên (nhỏ hơn), và tiếp tục như vậy cho đến khi chỉ còn lại một bài toán cuối cùng trong ngăn xếp, đó chính là bài toán gốc.
Đây là một đặc điểm thú vị của đệ quy và có nhiều ứng dụng trong thiết kế giải thuật, như thuật toán quay lui, nhánh cận và nhiều thuật toán khác.
V. Đệ quy đơn và đệ quy nhị phân
Hàm đệ quy có nhiều loại khác nhau trong lập trình nói chung và lập trình C++ nói riêng. Có thể chia đệ quy thành 6 loại sau:
Đệ quy đơn (đệ quy tuyến tính): Là loại đệ quy đơn giản nhất, trong đó chỉ có một lời gọi đệ quy trong hàm.
Đệ quy nhị phân: Là loại đệ quy mà hàm gọi lại chính nó hai lần hoặc gọi hai hàm đệ quy khác nhau.
Đệ quy đuôi: Là loại đệ quy mà lời gọi đệ quy được thực hiện ở cuối hàm.
Đệ quy đa tuyến: Là loại đệ quy mà hàm gọi lại chính nó nhiều lần trong cùng một lời gọi.
Đệ quy lồng: Là loại đệ quy trong đó một hàm đệ quy được gọi từ bên trong một hàm đệ quy khác.
Đệ quy tương hỗ: Là loại đệ quy trong đó hai hàm gọi lẫn nhau.
Thực tế, tên gọi của các loại đệ quy chỉ đơn giản là mô tả sự khác biệt về số lượng lời gọi đệ quy hoặc vị trí của lời gọi trong hàm. Các loại đệ quy khác hiếm khi được sử dụng, và chúng sẽ được đề cập trong các bài toán cụ thể sau này.
1. Đệ quy đơn
Còn gọi là đệ quy tuyến tính. Đây là dạng đệ quy dễ nhất và được sử dụng rất phổ biến trong lập trình. Đặc điểm của hàm đệ quy tuyến tính là chỉ có một lời gọi duy nhất tới chính nó bên trong thân hàm. Ví dụ, chúng ta đã biết hàm tính giai thừa n trong phần trước. Một ví dụ khác là tính tổng các số từ 1 đến n, cũng có thể sử dụng đệ quy tuyến tính như sau:
2. Đệ quy nhị phân
Đây là một dạng đệ quy nâng cao hơn, trong đó mỗi hàm đệ quy sẽ có một dòng lệnh gọi lại chính hàm đó hai lần. Hãy xem xét bài toán sau: Dãy số Fibonacci được định nghĩa theo công thức:
Tuy cách cài đặt đệ quy đơn giản nhưng nó có một số nhược điểm khiến nó không được khuyến khích trong việc lập trình. Để hiểu rõ hơn về ưu điểm và nhược điểm của đệ quy, cũng như khi nào nên sử dụng hàm đệ quy, chúng ta sẽ tiếp tục sang phần sau của chủ đề này.
VI. So sánh giữa cài đặt đệ quy và cài đặt không đệ quy
1. Từ bài toán dãy Fibonaci
Mọi bài toán có tính chất đệ quy đều có thể được chuyển đổi thành cách cài đặt không đệ quy. Thực tế, khi chương trình được biên dịch, các hàm đệ quy thường được dịch sang mã lệnh không đệ quy trước khi thực thi. Vì vậy, bài toán Fibonacci có thể được viết lại dưới dạng không đệ quy sử dụng một mảng một chiều như sau:
Nếu nhìn tổng quan về độ dài, cả hai giải thuật đệ quy và không đệ quy trong bài toán này có độ dài tương tự. Tuy nhiên, nếu xem xét về số lần tính toán, câu chuyện sẽ khác nhau đáng kể. Khi tính giá trị của F(5), giải thuật không đệ quy chỉ cần mất đúng 6 bước tính toán. Điều này xảy ra vì kết quả của các bài toán con sau khi tính toán sẽ được lưu trữ trong mảng một chiều và có thể được sử dụng trực tiếp cho các tính toán sau. Tuy nhiên, với giải thuật đệ quy, quá trình phân tách các bài toán con sẽ diễn ra như sau:
Khi tính giá trị của F(5), chương trình phải tính lại F(4) một lần, F(3) hai lần, F(2) ba lần, F(1) năm lần và F(0) ba lần. Điều này gọi là sự xuất hiện của các bài toán con gối nhau, dẫn đến việc chương trình tính toán lại nhiều lần cho cùng một bài toán trong khi thực tế chỉ cần tính một lần duy nhất. Điều này làm cho chương trình chạy chậm hơn đáng kể. Đối với các hàm đệ quy có nhiều lời gọi hơn, độ phức tạp tính toán sẽ tăng lên một cách đáng kể.
2. Có nên sử dụng đệ quy?
Đệ quy có nhược điểm về thời gian thực hiện nhưng vẫn có những ưu điểm riêng của nó. Nhờ cách cài đặt đơn giản và ngắn gọn, giải thuật đệ quy được áp dụng trong nhiều bài toán mà nếu sử dụng giải thuật lặp truyền thống sẽ rất khó để lập trình, ví dụ như giải thuật sắp xếp nhanh (quick sort). Trong những bài toán phức tạp, việc chuyển đổi giải thuật từ đệ quy sang phi đệ quy không phải lúc nào cũng đơn giản, nó đòi hỏi hiểu biết sâu về thuật toán và sự tinh tế trong cài đặt. Vì vậy, giải thuật đệ quy vẫn có giá trị và được sử dụng trong một số bài toán đặc biệt.
Tuy nhiên, tổng thể, ta nên cố gắng giới hạn việc sử dụng hàm đệ quy ở mức tối đa. Có nhiều phương pháp khác nhau để khử đệ quy, bao gồm quy hoạch động hoặc đệ quy có nhớ, mà chúng ta sẽ học về chúng trong các chuyên đề khác.
