Recursion
Bài đăng này đã không được cập nhật trong 7 năm
Đệ quy là gì ?
Đệ quy (tiếng Anh: recursion) là phương pháp dùng trong lập trình trong đó có chương trình được viết ra chứa các hàm từ gọi đến chính nó. Thuật toán đệ quy đi liền với một số bài toán nổi tiếng ví dụ như: Towers of Hanoi(TOH) , Inorder/Preorder/Postorder Tree Traversals, DFS of Graph
Điều kiện cơ bản trong đệ quy là gì?
Trong các bài toán đệ quy: các giải pháp cho các vấn đề đơn gian đã có từ đó giải quyết các bài toán phức tập hơn bằng cách chia bài toán thành các bài toán con đơn giản. Ví dụ:
def fact index
if index < = 1 // base case
return 1
else
return index * fact(index-1)
end
Như ví dụ trên base case của bài toán là nếu index < 1 thì kết quả trả về là 1từ đó đối với các trường hợp phức tạp hơn, số lớn hơn có thể được chia nhỏ để trở thành bài toán cơ bản đã được giải quyết.
Tại sao lỗi stack overflow lại xảy ra trong đệ quy?
Stack Overflow là một lỗi điển hình trong thuật toán đệ quy do chạy các vòng lặp quá sâu mà không thể tới được các bài toán cơ bản dẫn việc tràn bộ nhớ và chương trình sẽ thông báo gặp lỗi tràn bộ nhớ. Ví dụ:
// wrong base case (it may cause stack overflow).
def fact index
if index == 100
return 1
else
return index * fact(index-1)
end
Trong trường hợp fact(10) được gọi thì hàm fact sẽ được gọi với các tham sô fact(9), fact(8), fact(7), fact(6)...Nhưng với không thể gặp được base case(index == 100) và chương trình rơi vào một vòng lắp vô tận, cuối cùng khi bộ nhớ hết dung lượng lưu trữ nó sẽ gây ra stack overflow
Cũng có những trường hợp do việc xây dựng thuật toán chưa tốt cũng dẫn đến gặp stack overflow .
Phân việt giữa đệ quy trực tiếp và đệ quy gián tiếp
Đệ quy trực tiếp là một hàm khi gọi tới chính hàm đó. Đệ quy gián triếp như sau có một hàm A gọi tới một hàm B sau đó hàm B lại gọi lại hàm A. Ví dụ sau sẽ thể hiện sự khác biệt giữa đệ quy trực tiếp và đệ quy gián tiếp
// An example of direct recursion
void directRecFun()
{
// Some code....
directRecFun();
// Some code...
}
// An example of indirect recursion
void indirectRecFun1()
{
// Some code...
indirectRecFun2();
// Some code...
}
void indirectRecFun2()
{
// Some code...
indirectRecFun1();
// Some code...
}
Nhược điểm của đệ quy so với các thuật toán chạy một cách tuần tự
Lưu y rằng có những bài toán có thể giải bằng cả hai cách là đệ quy và chạy tuần tự. Có nghĩa là thuật toán đệ quy có thể được viết dưới dạng chạy tuần tự, ngược lại cùng đúng với cả chuyển từ tuần tự sang đệ quy. Tuy nhiên đệ quy lại yêu cầu cần có một không gian nhớ đủ lớn để chạy chương trình, yêu cần lớn hơn rất nhiều so với việc chạy tuần tự do tất cả các hàm được gọi đến phải chờ cho đến khi gặp được base case để trả kết quả về.
Ưu điểm của đệ quy so với các thuật toán chạy một cách tuần tự
Đệ quy sẽ giúp việc viết code trở nên gọn gàng đơn giản. Một số bài toán có tính đệ quy do đó phải sử dụng đệ quy để giải ví dụ duyệt cây, tháp Hà Nội, tuy nhiên cũng có thể giải bài toán trên với việc chạy tuần tự nhưng cần phải dùng thêm cả cấu trúc stack để lưu trữ.
Một số bài toán luyện tập
- Cài đặt thuật toán để hiển thị tất cả các cách sắp xếp hợp lệ của các cặp dấu '(' và ')' Ví dụ: input: 3 (có 3 cặp dấu) output: ()()(), ()(()), (())(), ((()))
def printChar l, r, str, count
if l < 0 || r < 0
return
elsif l == 0 && r == 0
puts str.join("")
else
if l > 0
str[count] = "("
printChar l - 1, r, str, count + 1
end
if r > l
str[count] = ")"
printChar l, r -1, str, count + 1
end
end
end
str = []
count = 3
printChar(count, count , str, 0)
- Cài đặt chức năng "paint fill" đây là chức năng có thể thấy được trong các ứng dụng xử lý ảnh. Giả sử màn hình vẽ được biểu diễn bởi ma trận 2 chiều với mỗi điểm chứa các con số đại diện cho màu tại vị trí tương ứng. Hãy chọn 1 vị trí rồi tô màu vào các vùng xung quanh cho đến khi gặp điểm có màu khác so với vị trí đầu tiên lựa chọn.\
screen = [
[1,1,1,1,1],
[1,1,1,1,1],
[1,2,2,2,2],
[1,2,1,1,1],
[1,2,1,1,1]
]
color = {red: 0, green: 1, blue: 2}
def paint_fill screen, x, y, old_color, new_color
if x < 0 || y < 0 || x >= screen.size || y >= screen[0].size
return false
end
if screen[x][y] == old_color
screen[x][y] = new_color
paint_fill screen, x -1, y, old_color, new_color # left
paint_fill screen, x +1, y, old_color, new_color # right
paint_fill screen, x, y - 1, old_color, new_color # top
paint_fill screen, x, y + 1, old_color, new_color # bottom
end
return true
end
paint_fill screen, 0, 0, screen[0][0], color[:red]
screen.each do |scr|
puts scr.join(" ")
end
- Cài đặt thuật toán để hiển thị số cách sắp xếp 8 quân hậu trên bàn cờ sao cho các quân hậu không thể chia sẻ cùng hàng, cùng cột cùng đường chéo.
@column_for_row = []
@count = 0
def print_chess_board
chess_board = [
["_","_","_","_","_","_","_","_"],
["_","_","_","_","_","_","_","_"],
["_","_","_","_","_","_","_","_"],
["_","_","_","_","_","_","_","_"],
["_","_","_","_","_","_","_","_"],
["_","_","_","_","_","_","_","_"],
["_","_","_","_","_","_","_","_"],
["_","_","_","_","_","_","_","_"]
]
@column_for_row.each_with_index do |col, index|
chess_board[index][col] = "Q"
end
chess_board.each do |scr|
puts scr.join " "
end
puts ""
@count += 1
end
def check row
(0...row).each do |i|
diff = (@column_for_row[row] - @column_for_row[i]).abs
return false if diff == 0 || diff == row - i
end
return true
end
def place_queen row
if row == 8
print_chess_board
else
8.times do |i|
@column_for_row[row] = i
if check row
place_queen row + 1
end
end
end
end
place_queen 0
puts "Number of way to arrange eight queens on a chess broad: #{@count}"
Tham khảo
http://www.geeksforgeeks.org/recursion/ Craking code interview
All rights reserved