Thuật toán đệ qui dưới đây tính:
Function Test (a,b: integer): integer;
Begin
If a = 0 then Test:=b
Else Test:= Test(b mod a, a);
End;
Trả lời:
Đáp án đúng: A
Đoạn code trên thực hiện thuật toán Euclid để tìm ước số chung lớn nhất (ƯCLN) của hai số nguyên a và b.
Giải thích:
* **Cơ sở đệ quy:** Khi `a = 0`, hàm trả về `b`. Điều này là do ƯCLN(0, b) = b.
* **Bước đệ quy:** Khi `a != 0`, hàm gọi đệ quy chính nó với các tham số mới là `b mod a` và `a`. Phép toán `b mod a` (b chia lấy dư cho a) là bước quan trọng trong thuật toán Euclid. Theo tính chất của ƯCLN, ƯCLN(a, b) = ƯCLN(b mod a, a).
Ví dụ:
Giả sử `Test(15, 25)` được gọi:
1. `Test(15, 25)`: Vì `a = 15 != 0`, nên gọi `Test(25 mod 15, 15)` tức `Test(10, 15)`.
2. `Test(10, 15)`: Vì `a = 10 != 0`, nên gọi `Test(15 mod 10, 10)` tức `Test(5, 10)`.
3. `Test(5, 10)`: Vì `a = 5 != 0`, nên gọi `Test(10 mod 5, 5)` tức `Test(0, 5)`.
4. `Test(0, 5)`: Vì `a = 0`, nên trả về `b = 5`.
Vậy, `Test(15, 25)` trả về 5, là ƯCLN của 15 và 25.
Do đó, đáp án đúng là A.
