Recursion in Ruby

Bài đăng này đã không được cập nhật trong 8 năm

1. Giới thiệu

Đệ quy là gì?

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).
Graham, Ronald; Donald Knuth; Oren Patashnik (1990). Concrete Mathematics. Chapter 1: Recurrent Problems.

Ví dụ mã giả đệ quy

def sum_array
  if the array is empty
    return 0
  else
    head of array + sum_array(tail of array)
  end
end

Quan sát ví dụ tính tổng các phần tử trong mảng.

Flow cơ bản của hàm đệ quy trên như sau:

Thực hiện một số thao tác với phần tử đầu tiên trong mảng.
Gọi chức năng tương tự với các phần tử còn lại của mảng.
Có điều kiện để dừng quá trình gọi đệ quy khi đã đạt được kết quả mong muốn.

Dưới đây là một ví dụ kết quả của đoạn mã giả trên.

array = [1,2,3,4,5]

1 + 2 + 3 + 4 + 5
1 + 2 + 3 + 9
1 + 2 + 12
1 + 14
15

Recursion vs Iteration

Trong Ruby người ta thường tránh sử dụng đệ quy và sử dụng vòng lặp để thay thế, Ruby có cấu trúc ngôn ngữ rất hữu dụng để hỗ trợ iteration trên dữ liệu. Recursion có thể kết thúc chậm hơn và tốn nhiều tài nguyên hơn so với Iteration. Trên Stack Overflow cũng có một số thảo luận về vấn đề này tại đây

Ở một số ngôn ngữ, đặc biệt là các ngôn ngữ lập trình chức năng (functional languages) đối với dữ liệu không thay đổi (immutable data) Elixir, Haskell ... Không có cấu trúc ngôn ngữ nào có thể giải quyết tất cả bằng iteration mà phải thực hiện thông qua đệ quy. Những ngôn ngữ này được tối ưu hóa cho đệ quy bằng việc sử dụng kỹ thuật tối ưu hóa tail callvà đi kèm với là thuật toán đối sánh mẫu pattern matching để giải quyết vấn đề head and tails của mảng. (Bạn có thể đọc thêm tại tails call và parttern matching)

Why recursion in Ruby

Bỏ qua những vấn đề tôi đã nói ở trên, tôi muốn nhìn thấy những gì recursion thực hiện để giải quyết một số vấn đề trong Ruby. Tôi sử dụng kỹ thuật monkey patching để thêm một method head_tail cho class Array.

class Array
  def head_tail
    head, *tail = *self
    [head, tail]
  end
end

Ví dụ: Array [1,2,3,4,5], the head is 1 and the tail is [2,3,4,5].

Recursion Examples

Factorials

Tính 6!, kết quả sẽ là 6 * 5 * 4 * 3 * 2 * 1

def recur_fact(num)
  if num == 0 || num == 1
    1
  else
    num * recur_fact(num - 1)
  end
end

recur_fact(6) # 720

Với iteration.

def iter_fact(num)
  if num == 0 || num == 1
    1
  else
    sum = 1
    num.times do |n|
      sum *= (n + 1)
    end
    sum
  end
end

iter_fact(6) # 720

Summing Array

def recur_sum(array)
  if array.empty?

  else
    head, tail = array.head_tail
    head + recur_sum(tail)
  end
end

recur_sum([1,2,3,4,5]) # 15

Với Iteration

def iter_sum(array)
  sum = 0
  array.each do |elem|
    sum += elem
  end
  sum
end

iter_sum([1,2,3,4,5]) # 15

Mapping Array

def recur_map(array, f)
  if array.empty?
    []
  else
    head, tail = array.head_tail
    [f.(head)] + recur_map(tail, f)
  end
end

recur_map([1,2,3,4,5], ->(elem) {
  elem * elem
}) # [1, 4, 9, 16, 25]

Với iteration

def iter_map(array, f)
  new_array = []
  array.each do |elem|
    new_array << f.(elem)
  end
  new_array
end

iter_map([1,2,3,4,5], ->(elem) {
  elem * elem
}) # [1, 4, 9, 16, 25]

Reducing Array

def recur_reduce(array, acc, f)
  if array.empty?
    acc
  else
    head, tail = array.head_tail
    recur_reduce(tail, f.(acc, head), f)
  end
end

# Join
recur_reduce(["Leigh", "Christopher", "Halliday"], "", ->(r, elem) {
  "#{r} #{elem}".strip
}) # "Leigh Christopher Halliday"

# Sum
recur_reduce([1,2,3,4,5], 0, ->(r, elem) {
  r + elem
}) # 15

# Longest String
recur_reduce(["Leigh", "Christopher", "Halliday"], "", ->(r, elem) {
  r.length > elem.length ? r : elem
}) # "Christopher"

# Count
recur_reduce(["Leigh", "Christopher", "Halliday"], 0, ->(r, elem) {
  r + 1
}) # 3

# Map
recur_reduce([1,2,3,4,5], [], ->(r, elem) {
  r + [elem * elem]
}) # [1, 4, 9, 16, 25]

Tổng kết

Trên đây là bài tìm hiểu chung về đệ quy và đệ quy trong Ruby, mong nhận được sự góp ý tích cực của mọi người.

Tham khảo

https://www.leighhalliday.com/recursion-in-ruby

https://viblo.asia/thanhnc/posts/zoZVRg9LGmg5

http://kipalog.com/posts/Gioi-thieu-ve-Pattern-Matching-trong-Elixir