Cơ bản về cấu trúc dữ liệu và giải thuật – Phần một: Đệ quy

Cấu trúc dữ liệu và giải thuật đóng vai trò quan trọng trong việc kết hợp thuật toán để đưa ra cách giải quyết bài toán. Một bài toán bất kỳ đều bao gồm các đối tượng dữ liệu và các yêu cầu xử lý trên những đối tượng đó. Do đó cần phải xây dựng lên một cấu trúc dữ liệu phù hợp trên các đối tượng nhằm phản ánh quan hệ giữa các đối tượng và hình thành giải thuật là các thao tác trên các đối tượng dữ liệu.


Giải thuật đệ quy
Đệ quy (Recursion) là một trong những giải thuật rất quen thuộc trong lập trình. Một số bài toán buộc phải dùng đệ quy mới giải quyết được (như bài toán duyệt cây). Đệ quy là một giải thuật chứa thao tác gọi lại chính nó. Điều này giúp mô tả một dãy lớn các thao tác bằng một số thao tác ngắn gọn trong đó chứa thao tác gọi lại chính nó.

Hôm nay, chúng ta sẽ cùng tìm hiểu một số khái niệm cơ bản về giải thuật đệ quy và một số bài toán kinh điển sử dụng đệ quy.

Định nghĩa hàm đệ quy
Trong lập trình, một hàm được gọi là đệ quy khi nó gọi chính nó trong thân hàm.
Một hàm đệ quy f(n) được xác định dựa trên giản đồ sau:
Phần cơ bản: Điều kiện thoát khỏi đệ quy, bao gồm một giá trị hoặc một tập giá trị ban đầu: f(0),f(1),..
Phần đệ quy: Tính f(n+1) dựa trên một giá trị f(k) đã biết trước đó
Ví dụ:
Tính n! = (n-1)! * n
Dãy fibonacy: f(n) = f(n-1)+ f(n-2)

Giải thuật đệ quy
Là thuật toán gọi lại chính nó với tham số nhỏ hơn.
Phù hợp để xử lý các đối tượng định nghĩa đệ quy
Ngôn ngữ lập trình cấp cao cho phép người lập trình thiết kế các hàm và thủ tục đệ quy.
Thuật toán: RecAlg(n)
Giả sử giá trị f(một),f(2),..f(k) ban đầu đã biết
If n