Thuật toán đệ quy trong Pascal

Trong Pascal, ta có thể sử dụng thuật toán đệ quy để giải quyết các vấn đề phức tạp bằng cách chia nhỏ chúng thành các vấn đề con nhỏ hơn.

Cú pháp định nghĩa hàm đệ quy trong Pascal như sau:

function RecursiveFunc(param1: type1; param2: type2; ...): returnType;
begin
    // Trường hợp dừng đệ quy
    if (baseCase) then 
    begin
        // Trả về kết quả cho trường hợp dừng đệ quy
        Result := baseCaseResult;
    end
    // Trường hợp đệ quy
    else 
    begin
        // Gọi lại hàm đệ quy với các giá trị tham số khác
        Result := RecursiveFunc(subParam1, subParam2, ...);
    end;
end;

Trong đó, baseCase là điều kiện dừng đệ quy, baseCaseResult là kết quả trả về khi đạt đến điều kiện dừng đệ quy. Trong trường hợp không đạt đến điều kiện dừng đệ quy, hàm đệ quy sẽ gọi lại chính nó với các tham số khác để giải quyết vấn đề con.

Ví dụ, đây là một hàm đệ quy tính giai thừa trong Pascal:

function Factorial(n: Integer): Integer;
begin
    if (n = 0) then
    begin
        Result := 1;
    end
    else
    begin
        Result := n * Factorial(n - 1);
    end;
end;

Hàm này sử dụng điều kiện dừng đệ quy là nếu n bằng 0 thì trả về kết quả là 1, ngược lại thì gọi lại chính nó với tham số n - 1.

Dưới đây là một ví dụ cụ thể về thuật toán đệ quy trong Pascal để tính tổng các số từ 1 đến n:

function Sum(n: Integer): Integer;
begin
    // Trường hợp dừng đệ quy
    if (n = 0) then
    begin
        Result := 0;
    end
    // Trường hợp đệ quy
    else
    begin
        Result := n + Sum(n-1);
    end;
end;

Hàm này sử dụng thuật toán đệ quy để tính tổng các số từ 1 đến n. Điều kiện dừng đệ quy là nếu n bằng 0 thì trả về 0. Trong trường hợp đệ quy, hàm sẽ gọi lại chính nó với tham số n-1 và cộng n vào kết quả trả về.

Ví dụ, nếu ta gọi hàm Sum(5), kết quả trả về sẽ là 15 vì tổng các số từ 1 đến 5 là 1+2+3+4+5=15. Các bước tính toán như sau:

• Sum(5) = 5 + Sum(4)
• Sum(4) = 4 + Sum(3)
• Sum(3) = 3 + Sum(2)
• Sum(2) = 2 + Sum(1)
• Sum(1) = 1 + Sum(0)
• Sum(0) = 0

Khi đạt đến trường hợp dừng đệ quy với Sum(0), hàm trả về kết quả là 0. Quay lại các bước tính toán trước đó, ta có:

• Sum(1) = 1 + 0 = 1
• Sum(2) = 2 + 1 = 3
• Sum(3) = 3 + 3 = 6
• Sum(4) = 4 + 6 = 10
• Sum(5) = 5 + 10 = 15

Vì vậy, tổng các số từ 1 đến 5 là 15.