Giới thiệu về đệ quy

Truy vấn phân cấp và đệ quy trong SQL Server

Jasmin Ludolf

Content Developer

Đệ quy là gì?

Đệ quy là việc một thủ tục, chương trình con, hàm, hoặc thuật toán tự gọi chính nó một hoặc nhiều lần cho đến khi thỏa điều kiện dừng

Hình minh họa tính chất đệ quy: tự gọi lặp lại.

Ví dụ thực tế về đệ quy

Cây gia phả - Tìm tất cả người cha trong 5 đời gần nhất

Rút bài toán về bài toán nhỏ cùng loại
1. Bài toán tổng thể: Tìm đủ năm đời
2. Bài toán nhỏ: Tìm người cha, rồi cha của người cha, ...
Giới hạn số bước

Tính chất đệ quy của Tháp Hà Nội.

Sự thật về đệ quy

Ưu điểm:

Giải bài toán theo cách đệ quy
Dễ đọc và theo dõi
Có thể giới hạn bằng điều kiện dừng

Nhược điểm:

Thời gian chạy chậm

Ví dụ đệ quy - Tổng các số

Định nghĩa toán học

Tổng các số liên tiếp được định nghĩa đệ quy như sau:

number = 1 
    for iteration = 1
number = number + (iteration - 1) 
    for iteration > 1

Tổng các số đến 5 là:

1+2+3+4+5 = 15

Ví dụ đệ quy - Tổng các số

Đệ quy với SQL: Common Table Expression - CTE

WITH calculate_SumOfNumber AS
     ( -- Initial Query
    SELECT 1 AS iteration, 1 AS SumOfNumber

     UNION ALL
     -- Recursive Part 
     SELECT iteration + 1, SumOfNumber + (iteration + 1)
         FROM calculate_SumOfNumber

         WHERE iteration < 6
     )

SELECT SumOfNumber 
    FROM calculate_SumOfNumber

Hãy luyện tập!

Truy vấn phân cấp và đệ quy trong SQL Server