Recursion

Đệ 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

1. 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)

1. 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

1. 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