Recursion – Đệ quy

This page is under construction!

Bài viết gồm 2 phần:

Phần 1: Giới thiệu hàm đệ quy

Phần 2: Phân tích hàm đệ quy bằng các ví dụ dễ hiểu

Phần 1: Hàm đệ quy ( recursive function)

Hàm đệ quy là hàm tự gọi chính nó. Một ví dụ thường thấy trong hầu hết các cuốn sách nói về đệ quy là hàm tính giai thừa ( factorial )

def factorial(n):
    if n == 0 or n == 1:
        return 1
    else:
        return n * factorial(n - 1)

Ở đây chúng ta define hàm factorial(n) và gọi chính nó trong body của hàm. Tại sao lại làm được điều này, nhìn có vẻ mâu thuẫn nhưng hãy nhớ rằng hàm sẽ không được thực thi cho đến khi gọi nó vì vậy điều này hoàn toàn có thể làm được. Để hiểu rõ hơn xin đọc bài về Environment diagram ( chưa viết ).

Cấu trúc chung của một hàm đệ quy thường có 3 phần

1. Phần base case: Thường là phần mà input của nó là trường hợp đơn giản nhất của vấn đề có thể dễ dàng tìm ra được output của input này. Base case thường là điều kiện để dừng của hàm đệ quy
2. Xây dựng recursive call: Phần gọi hàm với input đơn giản hơn (simpler input) của tổng thể vấn đề. Input này sẽ ngày càng tiến gần đến base case (simplest input). Mấu chốt của việc xây dựng recursive call là tìm ra câu hỏi thích hợp cho vấn đề tổng thể và áp dụng câu hỏi đấy cho input đơn giản hơn.
   Ví dụ: để tính n! ta chỉ cần biết (n-1)! rồi nhân vs n giả định rằng chúng ta đã biết (n-1)! là gì
3. Sử dụng kết quả của recursive call để giải quyết toàn bộ vấn đề: Làm thế nào để giải quyết toàn bộ vấn đề với kết quả tìm được từ recursive call. Trong trường hợp tính n! ta chỉ việc lấy n * (n – 1)!

Phần 2: Phân tích hàm đệ quy bằng các ví dụ dễ hiểu – Làm thế nào để hiểu đệ quy là gì – Làm thế nào để giải quyết các vấn đề bằng tư duy đệ quy

[tobe continue]