Trong các sách lập trình đã nói nhiều, mình xin nhắc lại:
Một đối tượng được gọi là đệ quy nếu nó được mô tả thông qua định nghĩa của chính nó. Nghĩa là, các đối tượng này được định nghĩa một cách quy nạp từ những khái niệm đơn giản nhất cùng dạng với nó. Trong toán học và tin học có rất nhiều đối tượng như thế.
Ví dụ:
0! = 1
1! = 1
2! = 1! * 2
3! = 2! *3
4! = 3! *4
Thuật toán đệ quy được sử dụng nhiều trong lập trình, ưu điểm cho tốc độ thực thi rất nhanh, code gọn gàng. Những người có thể code đệ quy thường được đánh giá cao.
Bài toán liệt kê các subfolder trong một folder cũng phải sử dụng thuật toán đệ quy. Cứ trong mỗi folder tìm được, ta lại sử dụng chính nó để tìm kiếm tiếp bên trong folder tìm được ấy có folder nào nữa không,...
Trong topic này sẽ liệt kê các bài toán đệ quy từ dễ tới phức tạp để mọi người cùng làm quen và luyện tập.
Bài tập 1:
Cho n là số tự nhiên. Hãy xây dựng hàm tính tổng: F ( n ) = 0+1+2+...+n
Lời giải:
Bài tập 2: Cho n là số tự nhiên. Tính tổng:
\[ F ( n ) = 0^2 + 1^2 + 2^2+...+n^2 \]
Bài tập 3: Cho n là số tự nhiên. Tính tổng F ( n ) = 0! + 1! + 2! + ... + n!
Một đối tượng được gọi là đệ quy nếu nó được mô tả thông qua định nghĩa của chính nó. Nghĩa là, các đối tượng này được định nghĩa một cách quy nạp từ những khái niệm đơn giản nhất cùng dạng với nó. Trong toán học và tin học có rất nhiều đối tượng như thế.
Ví dụ:
0! = 1
1! = 1
2! = 1! * 2
3! = 2! *3
4! = 3! *4
Thuật toán đệ quy được sử dụng nhiều trong lập trình, ưu điểm cho tốc độ thực thi rất nhanh, code gọn gàng. Những người có thể code đệ quy thường được đánh giá cao.
Bài toán liệt kê các subfolder trong một folder cũng phải sử dụng thuật toán đệ quy. Cứ trong mỗi folder tìm được, ta lại sử dụng chính nó để tìm kiếm tiếp bên trong folder tìm được ấy có folder nào nữa không,...
Trong topic này sẽ liệt kê các bài toán đệ quy từ dễ tới phức tạp để mọi người cùng làm quen và luyện tập.
Bài tập 1:
Cho n là số tự nhiên. Hãy xây dựng hàm tính tổng: F ( n ) = 0+1+2+...+n
Lời giải:
Mã:
Sub test()
Dim i As Long
i = 10
MsgBox tinhtong(i)
End Sub
Function tinhtong(ByVal n) As Long
If n = 0 Then
tinhtong = 0
Exit Function
End If
tinhtong = tinhtong(n - 1) + n
End Function
\[ F ( n ) = 0^2 + 1^2 + 2^2+...+n^2 \]
Bài tập 3: Cho n là số tự nhiên. Tính tổng F ( n ) = 0! + 1! + 2! + ... + n!